摧毁高塔

英文题名：A. Destroying Towers
来源：Codeforces 2237A
比赛：Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
时间限制：1 second
空间限制：256 megabytes

题目描述

有 $n$ 座塔。你可以按任意顺序操作每座塔一次：操作第 $i$ 座塔时，会把右侧第一个当前高度严格大于它的塔削成相同高度。求最终高度总和的最小值。

输入格式

第一行输入 $t$。每组输入 $n$ 和 $n$ 个塔高 $a_i$。

输出格式

每组输出最小最终总高度。

样例

10
3
1 3 5
3
5 4 3
4
3 2 5 1
4
2 1 4 3
5
4 1 3 5 2
5
2 2 3 1 4
1
7
6
6 1 5 2 4 3
4
1 1 1 1
5
10 3 8 6 9

3
12
8
5
8
8
7
11
4
22