Multitest Generator
Contest: Codeforces Round 860 (Div. 2)
Difficulty rating: 2300
Tags: brute force, dp

Let's call an array $$$b_1, b_2, \ldots, b_m$$$ a test if $$$b_1 = m - 1$$$.

Let's call an array $$$b_1, b_2, \ldots, b_m$$$ a multitest if the array $$$b_2, b_3, \ldots, b_m$$$ can be split into $$$b_1$$$ non-empty subarrays so that each of these subarrays is a test. Note that each element of the array must be included in exactly one subarray, and the subarrays must consist of consecutive elements.

Let's define the function $$$f$$$ from the array $$$b_1, b_2, \ldots, b_m$$$ as the minimum number of operations of the form "Replace any $$$b_i$$$ with any non-negative integer $$$x$$$", which needs to be done so that the array $$$b_1, b_2, \ldots, b_m$$$ becomes a multitest.

You are given an array of positive integers $$$a_1, a_2, \ldots, a_n$$$. For each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, find $$$f([a_i, a_{i+1}, \ldots, a_n])$$$.

Below are some examples of tests and multitests.

- Tests: $$$[\underline{1}, 5]$$$, $$$[\underline{2}, 2, 2]$$$, $$$[\underline{3}, 4, 1, 1]$$$, $$$[\underline{5}, 0, 0, 0, 0, 0]$$$, $$$[\underline{7}, 1, 2, 3, 4, 5, 6, 7]$$$, $$$[\underline{0}]$$$. These arrays are tests since their first element (underlined) is equal to the length of the array minus one.
- Multitests: $$$[1, \underline{\underline{1}, 1}]$$$, $$$[2, \underline{\underline{3}, 0, 0, 1}, \underline{\underline{1}, 12}]$$$, $$$[3, \underline{\underline{2}, 2, 7}, \underline{\underline{1}, 1}, \underline{\underline{3}, 4, 4, 4}]$$$, $$$[4, \underline{\underline{0}}, \underline{\underline{3}, 1, 7, 9}, \underline{\underline{4}, 2, 0, 0, 9}, \underline{\underline{1}, 777}]$$$. Underlined are the subarrays after the split, and double underlined are the first elements of each subarray.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 300\,000$$$) — 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 300\,000$$$) — elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.

Output format:
For each test case print $$$n - 1$$$ numbers — $$$f([a_i, a_{i+1}, \ldots, a_n])$$$ for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$.

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

Note:
In the first test case of the first test the array $$$[1, 2, 1, 7]$$$ is a multitest since the array $$$[2, 1, 7]$$$ is a test. The array $$$[2, 1, 7]$$$ is not a multitest, but after replacing the first number with $$$1$$$, an array $$$[1, 1, 7]$$$ is obtained, which is a multitest. The array $$$[1, 7]$$$ is also not a multitest, but the array $$$[1, 0]$$$ is, so $$$f([1, 7]) = 1$$$.

In the second test case of first test, for $$$i = 2$$$, $$$f([a_i, a_{i+1}, \ldots, a_n]) = f([1, 3, 1, 2, 1, 1]) = 1$$$, since the array itself is not a multitest, but after replacing the second element with $$$4$$$ you get multitest.

In the third test case of first test, for $$$i = 1$$$, $$$f([a_i, a_{i+1}, \ldots, a_n]) = f([2, 7, 1, 1]) = 1$$$, since the array itself is not a multitest, but after replacing the second element with $$$0$$$ you get multitest.

The second test is an array composed of all the numbers of the first test. Therefore $$$f([a_1, a_2, \ldots, a_n])$$$ naturally equals to $$$0$$$.

Example input:
3
4
1 2 1 7
7
3 1 3 1 2 1 1
4
2 7 1 1

Example output:
0 1 1 
0 1 1 0 1 1 
1 1 1

Example input:
1
19
3 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1

Example output:
0 0 1 1 1 1 1 1 1 0 1 0 1 0 2 1 1 1

Editorial:
The first idea: you can make a multitest from any array using $$$2$$$ operations. To do this, replace the first element with $$$1$$$, and the second with $$$n - 2$$$, where $$$n$$$ is the length of the array.
It remains to learn how to determine whether it is possible to make a multitest from an array for $$$0$$$ and for $$$1$$$ change.
First let's deal with the $$$0$$$ changes.
Question: when is the array $$$a_i, \ldots, a_n$$$ a multitest? Answer: when $$$a_{i+1}, \ldots, a_n$$$ represents exactly $$$a_i$$$ of tests written in a row.
For convenience, let's call the index $$$i$$$ good if $$$a_i, \ldots, a_n$$$ represents a certain number of tests written in a row. For all indexes, we want to find out if they are good, and if so, how many tests the corresponding suffix consists of. Denote $$$go_i = i + a_i + 1$$$. The logic is that if $$$i$$$ is the first element of a certain test, then $$$go_i$$$ is the first element of the next test. Then the index $$$i$$$ will be good if the chain $$$i \to go_i \to go_{go_i} \to \ldots$$$ ends in $$$n + 1$$$. To find out if this chain ends in $$$n + 1$$$ and if so, how many tests it consists of can be simple dynamic programming by suffixes. In total, to determine whether the suffix $$$a_i, \ldots, a_n$$$ is a multitest in itself, it is necessary to check that $$$i+1$$$ is good and its suffix consists of exactly $$$a_i$$$ tests.
Now it remains to determine whether it is possible to make a multitest for $$$1$$$ change. If the array has become a multitest after the change, then the element responsible for either the number of tests or the first element of some test has been changed.
Case one: the number of tests changes. Then the array can be made a multitest if and only if $$$i + 1$$$ is a good index.
Case two: the index after the change will become the first element of some test. We will consider "the maximum number of tests that can be achieved by changing one element" as the dynamics of the suffix. Then one change can make the suffix a multitest if the dynamics value from $$$i+1$$$ is greater than or equal to $$$a_i$$$. How to calculate this dynamics for $$$i+1$$$: The index being changed then must be one of $$$i+1$$$, $$$go_{i+1}$$$, $$$go_{go_{i+1}}$$$, $$$\ldots$$$, otherwise the test chain of $$$i+1$$$ will remain the same and the change will not affect anything. Then if $$$go_{i+1}, go_{go_{i+1}}, \ldots$$$ changes, then this change will be reflected in the dynamics value from $$$go_{i+1}$$$, through which it can be recalculated. And if $$$i+1$$$ changes, then you need to make a change so that $$$go_{i+1}$$$ is a good index (after the change). $$$go_{i+1}$$$ can become any index of $$$\geq i+2$$$ after the change. And of all these, you need to choose a good index with the maximum number of tests. This value can be maintained separately when recalculating the dynamics.