CF1798E.Multitest Generator

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.

我们称一个数组 $b_1, b_2, \ldots, b_m$ 为测试数组（test），当且仅当 $b_1 = m - 1$。

我们称一个数组 $b_1, b_2, \ldots, b_m$ 为多重测试数组（multitest），当且仅当子数组 $b_2, b_3, \ldots, b_m$ 可以被划分为 $b_1$ 个非空子数组，使得每个子数组均为测试数组。注意：原数组中的每个元素必须且仅被包含在其中一个子数组中，且这些子数组必须由连续的元素构成。

我们定义函数 $f$ 作用于数组 $b_1, b_2, \ldots, b_m$，其值为：使该数组变为多重测试数组所需的最少操作次数；每次操作的形式为“将任意 $b_i$ 替换为任意非负整数 $x$”。

给定一个正整数数组 $a_1, a_2, \ldots, a_n$。对每个 $i$（从 $1$ 到 $n - 1$），求 $f([a_i, a_{i+1}, \ldots, a_n])$。

以下是一些测试数组与多重测试数组的示例：

• 测试数组：$[\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}]$。这些数组均为测试数组，因为其首元素（已加下划线）等于数组长度减一。
• 多重测试数组：$[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}]$。其中单下划线标出了划分后的各子数组，双下划线标出了每个子数组的首元素。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 300\,000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 300\,000$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 300\,000$）—— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $300\,000$。

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$.

对每个测试用例，输出 $n - 1$ 个数——即对每个从 $1$ 到 $n - 1$ 的 $i$，输出 $f([a_i, a_{i+1}, \ldots, a_n])$。

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$.

在第一组测试的第一个测试用例中，数组 $[1, 2, 1, 7]$ 是一个多测数组（multitest），因为其子数组 $[2, 1, 7]$ 是一个测试数组（test）。数组 $[2, 1, 7]$ 本身不是多测数组，但将第一个数替换为 $1$ 后，得到数组 $[1, 1, 7]$，该数组是多测数组。数组 $[1, 7]$ 也不是多测数组，但数组 $[1, 0]$ 是，因此 $f([1, 7]) = 1$。

在第一组测试的第二个测试用例中，当 $i = 2$ 时，$f([a_i, a_{i+1}, \ldots, a_n]) = f([1, 3, 1, 2, 1, 1]) = 1$，因为该数组本身不是多测数组，但将第二个元素替换为 $4$ 后可得到一个多测数组。

在第一组测试的第三个测试用例中，当 $i = 1$ 时，$f([a_i, a_{i+1}, \ldots, a_n]) = f([2, 7, 1, 1]) = 1$，因为该数组本身不是多测数组，但将第二个元素替换为 $0$ 后可得到一个多测数组。

第二组测试是由第一组测试中所有数字组成的数组。因此 $f([a_1, a_2, \ldots, a_n])$ 自然等于 $0$。