CF2237A.Destroying Towers

Quack the Duck has returned to his homeland and found $n$ towers standing in a line. The height of the $i$-th tower is $a_i$. He wants vengeance for the destruction of his ecosystem, and has vowed to wreak as much havoc as possible with his laser gun.

Quack will operate on each tower exactly once, in any order he chooses. The operation on tower $i$ is as follows:

• Quack climbs to the top of tower $i$ and shoots a laser to the right, cutting the first taller tower it hits down to the same height as tower $i$.

  Formally, let $j$ be the smallest index such that $j \gt i$ and $a_j \gt a_i$, where $a_i$ and $a_j$ are the current heights of the towers. If such $j$ exists, then $a_j$ is replaced with $a_i$. Otherwise, nothing happens.

Find the minimum possible final sum of tower heights over all possible orders of operations.

鸭子奎克回到了他的故乡，发现有 $n$ 座塔排成一列。第 $i$ 座塔的高度为 $a_i$。他决心为自身生态环境所遭受的破坏复仇，并发誓要用他的激光枪制造尽可能大的混乱。

奎克将恰好对每座塔执行一次操作，且操作顺序可由他任意选择。对第 $i$ 座塔的操作如下：

• 奎克爬上第 $i$ 座塔的顶端，向右发射一道激光，将第一个被击中的、比当前塔更高的塔削至与第 $i$ 座塔等高。

  形式化地，令 $j$ 为满足 $j > i$ 且 $a_j > a_i$ 的最小下标（其中 $a_i$ 和 $a_j$ 表示各塔当前的高度）。若这样的 $j$ 存在，则将 $a_j$ 替换为 $a_i$；否则，不进行任何操作。

求在所有可能的操作顺序下，塔的最终高度之和的最小可能值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1\le n\le 100$) — the number of towers.

The following line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 1000$) — the heights of the towers.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）—— 各塔的高度。

For each test case, output a single integer — the minimum possible final sum of tower heights over all possible orders of operations.

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

In the first test case, one optimal order is $3,1,2$. The heights change as follows:

\[1,3,5\]\\to \[1,3,5\]\\to \[1,1,5\]\\to \[1,1,1\].

Thus the final sum is $1+1+1=3$.

In the second test case, no operation can change any tower. For every tower, there is no higher tower to its right. Therefore the final heights remain $[5,4,3]$, and the answer is $5+4+3=12$.

In the third test case, one optimal order is $4,1,3,2$. The heights change as follows:

\[3,2,5,1\]\\to \[3,2,5,1\]\\to \[3,2,3,1\]\\to \[3,2,3,1\]\\to \[3,2,2,1\].

Therefore the final sum is $3+2+2+1=8$.

在第一个测试用例中，一种最优的操作顺序是 $3,1,2$。塔的高度变化如下：

\[1,3,5\]\\to \[1,3,5\]\\to \[1,1,5\]\\to \[1,1,1\].

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

在第二个测试用例中，没有任何操作能改变任意一座塔。对于每座塔，其右侧均不存在更高的塔。因此最终高度仍为 $[5,4,3]$，答案为 $5+4+3=12$。

在第三个测试用例中，一种最优的操作顺序是 $4,1,3,2$。塔的高度变化如下：

\[3,2,5,1\]\\to \[3,2,5,1\]\\to \[3,2,3,1\]\\to \[3,2,3,1\]\\to \[3,2,2,1\].

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