给定一个整数数组 $$$a$$$,长度为 $$$n$$$。
您可以多次应用以下操作(可能为零):
- 首先,选择一个整数 $$$k$$$,使得 $$$1 \le k \le n$$$ 并支付 $$$k + 1$$$ 硬币。
- 然后,精确选择 $$$k$$$ 索引,使得 $$$1 \le i_1 < i_2 < \ldots < i_k \le n$$$。
- 然后,对于从$$$1$$$到$$$k$$$的每个$$$x$$$,将$$$a_{i_x}$$$增加$$$1$$$。
求使 $$$a$$$ 不减少所需的最小硬币数量。即 $$$a_1 \le a_2 \le \ldots \le a_n$$$。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - 使 $$$a$$$ 不减少所需的最小硬币数量。
示例
输入 #1
5 3 1 7 9 5 2 1 4 7 6 4 1 3 2 4 1 179 9 344 12 37 60 311 613 365 328 675
输出 #1
0 3 2 0 1821
注意
在第一个测试用例中,$$$a$$$ 已经排序,因此您不必花费任何硬币。
在第二个测试用例中,最佳操作顺序是:
- 选择 $$$k = 2$$$ 以及索引 $$$2$$$ 和 $$$5$$$:$$$[ 2, \color{red}{1}, 4, 7, \color{red}{6} ] \rightarrow [2, 2, 4, 7, 7]$$$。这需要 $$$3$$$ 硬币。