← 返回题目列表

Codeforces · 1604/A

A. 时代

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

Shohag 有一个整数序列 $$$a_1, a_2, \ldots, a_n$$$。他可以执行以下操作任意次数(可能为零):

- 选择任何正整数$$$k$$$(在不同的操作中可以不同)。
- 选择序列中的任意位置(可能是序列的开头或结尾,或者任意两个元素之间)并将 $$$k$$$ 插入序列中的该位置。
- 这样,序列 $$$a$$$ 发生变化,并且对这个变化的序列执行下一个操作。

例如$$$a=[3,3,4]$$$,选择$$$k = 2$$$,则运算后可以得到序列$$$[\underline{2},3,3,4]$$$、$$$[3,\underline{2},3,4]$$$之一, $$$[3,3,\下划线{2},4]$$$,或$$$[3,3,4,\下划线{2}]$$$。

Shohag 希望这个序列满足以下条件:对于每个 $$$1 \le i \le |a|$$$,$$$a_i \le i$$$。这里,$$$|a|$$$表示$$$a$$$的大小。

帮助他找到实现这一目标所需执行的最少操作数。我们可以证明,在问题的约束下,总是可以通过有限数量的操作来实现这一目标。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 序列的初始长度。

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

输出

对于每个测试用例,打印一个整数 - 实现声明中提到的目标所需执行的最少操作数。

示例

输入 #1

4
3
1 3 4
5
1 2 5 7 4
1
1
3
69 6969 696969

输出 #1

1
3
0
696966

注意

在第一个测试用例中,我们必须执行至少一个操作,如 $$$a_2=3>2$$$。我们可以执行 $$$[1, 3, 4] \rightarrow [1, \underline{2}, 3, 4]$$$ 操作(新插入的元素带有下划线),现在条件满足了。

在第二个测试用例中,Shohag 可以执行以下操作:

$$$[1, 2, 5, 7, 4] \rightarrow [1, 2, \underline{3}, 5, 7, 4] \rightarrow [1, 2, 3, \underline{4}, 5, 7, 4] \rightarrow [1, 2, 3, 4, 5, \underline{3}, 7, 4]$$$。

在第三个测试用例中,序列已经满足条件。