Add Zeros
Contest: Codeforces Round 982 (Div. 2)
Difficulty rating: 1500
Tags: brute force, data structures, dfs and similar, dp, graphs, greedy

You're given an array $$$a$$$ initially containing $$$n$$$ integers. In one operation, you must do the following:

- Choose a position $$$i$$$ such that $$$1 < i \le |a|$$$ and $$$a_i = |a| + 1 - i$$$, where $$$|a|$$$ is the current size of the array.
- Append $$$i - 1$$$ zeros onto the end of $$$a$$$.

After performing this operation as many times as you want, what is the maximum possible length of the array $$$a$$$?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the maximum possible length of $$$a$$$ after performing some sequence of operations.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can first choose $$$i = 4$$$, since $$$a_4 = 5 + 1 - 4 = 2$$$. After this, the array becomes $$$[2, 4, 6, 2, 5, 0, 0, 0]$$$. We can then choose $$$i = 3$$$ since $$$a_3 = 8 + 1 - 3 = 6$$$. After this, the array becomes $$$[2, 4, 6, 2, 5, 0, 0, 0, 0, 0]$$$, which has a length of $$$10$$$. It can be shown that no sequence of operations will make the final array longer.

In the second test case, we can choose $$$i=2$$$, then $$$i=3$$$, then $$$i=4$$$. The final array will be $$$[5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0]$$$, with a length of $$$11$$$.

Example input:
4
5
2 4 6 2 5
5
5 4 4 5 1
4
6 8 2 3
1
1

Example output:
10
11
10
1

Editorial:
Let's rearrange the equation given in the statement to find a 'required' $$$|a|$$$ value in order to use an operation at that index. We have $$$a_i = |a| + 1 - i$$$, so $$$|a| = a_i + i - 1$$$. Note that if $$$a_i = 0$$$, then the condition is never true, since $$$i - 1 < |a|$$$ always. So actually, we just need to consider the first $$$n$$$ positions.
Once we use an operation at position $$$i$$$, the length of the array will increase by $$$i - 1$$$. So, for each position we require some length $$$u_i = a_i + i - 1$$$ and make a length of $$$v_i = u + i - 1$$$. So, let's create a graph containing all $$$n$$$ edges, and run some DFS or BFS on this graph starting from node $$$n$$$ (the starting value of $$$|a|$$$). It then follows that the largest node visited is the maximum length of the array we can possibly get.
We should use a map to store the graph, since the length of the array can grow up to $$$\approx n^2$$$ and so the graph is very sparse. If we don't want to use a map, we can also take advantage of the fact that all edges are directed from $$$u_i$$$ to $$$v_i$$$ where $$$u_i < v_i$$$ and that all edges and nodes are fixed, so we can actually iterate through all $$$u_i$$$ and maintain a boolean array of which $$$v_i$$$ values are visited so far, updating it at any point using a binary search.