← 返回题目列表

Codeforces · 1856/A

A. 某种故事

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

Alphen 有一个正整数数组 $$$a$$$,长度为 $$$n$$$。

Alphen 可以执行以下操作:

- 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$,将 $$$a_i$$$ 替换为 $$$\max(0, a_i - 1)$$$。

Alphen将执行上述操作,直到$$$a$$$排序完毕,即$$$a$$$满足$$$a_1 \leq a_2 \leq \ldots \leq a_n$$$。 Alphen 将执行多少次手术?在问题的约束下,可以证明Alphen将执行有限数量的操作。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10 ^ 9$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,输出一个整数 - Alphen 将执行的操作数。

示例

输入 #1

7
3
1 2 3
5
2 1 2 1 2
4
3 1 5 4
2
7 7
5
4 1 3 2 5
5
2 3 1 4 5
3
1000000000 1 2

输出 #1

0
2
5
0
4
3
1000000000

注意

在第一个测试用例中,我们有 $$$a=[1,2,3]$$$。由于 $$$a$$$ 已经排序,Alphen 不需要执行任何操作。所以,答案是$$$0$$$。

在第二个测试用例中,我们有 $$$a=[2,1,2,1,2]$$$。由于 $$$a$$$ 最初并未排序,Alphen 将执行一个操作来使 $$$a=[1,0,1,0,1]$$$。执行一次操作后,$$$a$$$仍未排序,因此Alphen将执行另一次操作,使$$$a=[0,0,0,0,0]$$$。由于 $$$a$$$ 已排序,Alphen 不会执行任何其他操作。由于 Alphen 总共执行了两次操作,因此答案是 $$$2$$$。