← 返回题目列表

Codeforces · 2237/A

A. 摧毁塔

中文机器翻译题面 查看原题

嘎嘎鸭回到了他的家乡,发现了 $$$n$$$ 塔排成一排。第 $$$i$$$ 塔的高度为 $$$a_i$$$。他想要为生态系统遭到破坏而复仇,并发誓要用他的激光枪造成尽可能多的破坏。

庸医将在每座塔上运行 正好一次,按照他选择的任何顺序。对塔$$$i$$$的操作如下:

  • 嘎嘎爬到塔顶 $$$i$$$ 并向右侧发射激光,将其击中的第一个较高塔切割至与塔 $$$i$$$ 相同的高度。

    正式地,令 $$$j$$$ 为满足 $$$j \gt i$$$ 和 $$$a_j \gt a_i$$$ 的最小索引,其中 $$$a_i$$$ 和 $$$a_j$$$ 是塔的当前高度。如果这样的$$$j$$$存在,则$$$a_j$$$被替换为$$$a_i$$$。否则,什么也不会发生。

找出所有可能的操作顺序中塔高度的最小可能最终总和。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 100$$$) — 塔的数量。

以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 1000$$$) — 塔的高度。

输出

对于每个测试用例,输出一个整数 - 所有可能的操作顺序的塔高度的最小可能最终总和。

示例

输入
复制

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

注意

在第一个测试用例中,一个最佳顺序是 $$$3,1,2$$$。高度变化如下:

$$[1,3,5]\到 [1,3,5]\到 [1,1,5]\到 [1,1,1].$$

因此最终的总和是$$$1+1+1=3$$$。

在第二个测试用例中,任何操作都无法更改任何塔。对于每座塔,其右侧都没有更高的塔。因此最终的高度仍然是$$$[5,4,3]$$$,答案是$$$5+4+3=12$$$。

在第三个测试用例中,一个最佳顺序是 $$$4,1,3,2$$$。高度变化如下:

$$[3,2,5,1]\到 [3,2,5,1]\到 [3,2,3,1]\到 [3,2,3,1]\到 [3,2,2,1].$$

因此最终的总和是$$$3+2+2+1=8$$$。