← 返回题目列表

Codeforces · 1987/B

B. K 排序

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

给定一个整数数组 $$$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$$$ 硬币。