CF2237A Destroying Towers

鸭子 Quack 回到了家乡，发现有 $n$ 座高塔排成一行，第 $i$ 座高塔的高度为 $a_i$。他为了报复生态系统遭到破坏，发誓要用他的激光枪造成尽可能多的破坏。 Quack 会对每一座高塔恰好操作一次，顺序可以自行选择。对于第 $i$ 座塔的操作如下： - Quack 会爬到第 $i$ 座塔顶端，向右侧发射激光，将遇到的第一个比它高的高塔的高度削减到与第 $i$ 座塔相同。形式化地，记 $j$ 是满足 $j > i$ 且 $a_j > 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$），表示每座高塔的高度。

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

在第一个测试用例中，最优操作顺序为 $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$。 由 ChatGPT 5 翻译