给定一个数组 $$$a$$$,最初包含 $$$n$$$ 整数。在一项操作中,您必须执行以下操作:
- 选择一个位置 $$$i$$$ 使得 $$$1 < i \le |a|$$$ 并且 $$$a_i = |a| + 1 - i$$$,其中 $$$|a|$$$ 是数组的当前大小。
- 将 $$$i - 1$$$ 零附加到 $$$a$$$ 的末尾。
多次执行此操作后,数组 $$$a$$$ 的最大可能长度是多少?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 执行某些操作序列后 $$$a$$$ 的最大可能长度。
示例
输入 #1
4 5 2 4 6 2 5 5 5 4 4 5 1 4 6 8 2 3 1 1
输出 #1
10 11 10 1
注意
在第一个测试用例中,我们可以首先选择$$$i = 4$$$,因为$$$a_4 = 5 + 1 - 4 = 2$$$。此后,数组变为 $$$[2, 4, 6, 2, 5, 0, 0, 0]$$$。然后我们可以选择 $$$i = 3$$$,因为 $$$a_3 = 8 + 1 - 3 = 6$$$。之后,数组就变成$$$[2, 4, 6, 2, 5, 0, 0, 0, 0, 0]$$$,长度为$$$10$$$。可以证明,任何操作序列都不会使最终的数组变得更长。
在第二个测试用例中,我们可以选择$$$i=2$$$,然后$$$i=3$$$,然后$$$i=4$$$。最终数组为 $$$[5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0]$$$,长度为 $$$11$$$。