嘎嘎鸭回到了他的家乡,发现了 $$$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$$$) — 塔的高度。
输出
对于每个测试用例,输出一个整数 - 所有可能的操作顺序的塔高度的最小可能最终总和。
示例
输入复制
1031 3 535 4 343 2 5 142 1 4 354 1 3 5 252 2 3 1 41766 1 5 2 4 341 1 1 1510 3 8 6 9
输出复制
3128588711422
注意
在第一个测试用例中,一个最佳顺序是 $$$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$$$。