Multitest Generator

题意翻译

称一个长度为 $n$ 的序列 $a$ 是一个 test 当且仅当 $a_1=n-1$。 称一个长度为 $n$ 的序列 $a$ 是一个 multitest 的当且仅当能够将 $a_2,a_3,\cdots,a_n$ 划分成 $a_1$ 个连续段，使得每个连续段都是一个 test。 给定长度为 $n$ 的序列 $a$，求对于 $i$ 从 $1$ 到 $n-1$，以 $i$ 开始的后缀至少修改几个值才能够成为 multitest。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

3
4
1 2 1 7
7
3 1 3 1 2 1 1
4
2 7 1 1

输出样例 #1

0 1 1 
0 1 1 0 1 1 
1 1 1

输入样例 #2

1
19
3 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1

输出样例 #2

0 0 1 1 1 1 1 1 1 0 1 0 1 0 2 1 1 1

说明

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

**Multitest Generator**

**题意翻译**
定义一个长度为 $n$ 的序列 $a$ 是一个 test 当且仅当 $a_1=n-1$。称一个长度为 $n$ 的序列 $a$ 是一个 multitest 的当且仅当能够将 $a_2,a_3,\cdots,a_n$ 划分成 $a_1$ 个连续段，使得每个连续段都是一个 test。给定长度为 $n$ 的序列 $a$，求对于 $i$ 从 $1$ 到 $n-1$，以 $i$ 开始的后缀至少修改几个值才能够成为 multitest。

**题目描述**
称一个数组 $ 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 $ 个非空子数组，使得每个子数组都是一个 test。注意数组的每个元素必须恰好包含在一个子数组中，且子数组必须由连续元素组成。

定义函数 $ f $ 对于数组 $ b_1, b_2, \ldots, b_m $ 为使数组 $ b_1, b_2, \ldots, b_m $ 成为 multitest 所需的最小操作数，操作形式为“将任何 $ b_i $ 替换为任何非负整数 $ x $”。

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

**输入输出格式**

**输入格式**
每个测试包含多个测试用例。第一行包含测试用例数 $ 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 $。

**输出格式**
对于每个测试用例，打印 $ n - 1 $ 个数字——对于每个 $ i $ 从 $ 1 $ 到 $ n - 1 $，输出 $ f([a_i, a_{i+1}, \ldots, a_n]) $。

**输入输出样例**

**输入样例 #1**
```
3
4
1 2 1 7
7
3 1 3 1 2 1 1
4
2 7 1 1
```
**输出样例 #1**
```
0 1 1
0 1 1 0 1 1
1 1 1
```
**输入样例 #2**
```
1
19
3 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1
```
**输出样例 #2**
```
0 0 1 1 1 1 1 1 1 0 1 0 1 0 2 1 1 1
```

**说明**
在第一个测试用例的第一个测试中，数组 $ [1, 2, 1, 7] $ 是一个 multitest，因为数组 $ [2, 1, 7] $ 是一个 test。数组 $ [2, 1, 7] $ 本身不是一个 multitest，但将第一个数字替换为 $ 1 $ 后，得到数组 $ [1, 1, 7] $，这是一个 multitest。数组 $ [1, 7] $ 也不是一个 multitest，但数组 $ [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 $，因为数组本身不是一个 multitest，但将第二个元素替换为 $**Multitest Generator** **题意翻译** 定义一个长度为 $n$ 的序列 $a$ 是一个 test 当且仅当 $a_1=n-1$。称一个长度为 $n$ 的序列 $a$ 是一个 multitest 的当且仅当能够将 $a_2,a_3,\cdots,a_n$ 划分成 $a_1$ 个连续段，使得每个连续段都是一个 test。给定长度为 $n$ 的序列 $a$，求对于 $i$ 从 $1$ 到 $n-1$，以 $i$ 开始的后缀至少修改几个值才能够成为 multitest。 **题目描述** 称一个数组 $ 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 $ 个非空子数组，使得每个子数组都是一个 test。注意数组的每个元素必须恰好包含在一个子数组中，且子数组必须由连续元素组成。 定义函数 $ f $ 对于数组 $ b_1, b_2, \ldots, b_m $ 为使数组 $ b_1, b_2, \ldots, b_m $ 成为 multitest 所需的最小操作数，操作形式为“将任何 $ b_i $ 替换为任何非负整数 $ x $”。 给定一个正整数数组 $ a_1, a_2, \ldots, a_n $。对于每个 $ i $ 从 $ 1 $ 到 $ n - 1 $，求 $ f([a_i, a_{i+1}, \ldots, a_n]) $。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含测试用例数 $ 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 $。 **输出格式** 对于每个测试用例，打印 $ n - 1 $ 个数字——对于每个 $ i $ 从 $ 1 $ 到 $ n - 1 $，输出 $ f([a_i, a_{i+1}, \ldots, a_n]) $。 **输入输出样例** **输入样例 #1** ``` 3 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1 ``` **输出样例 #1** ``` 0 1 1 0 1 1 0 1 1 1 1 1 ``` **输入样例 #2** ``` 1 19 3 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1 ``` **输出样例 #2** ``` 0 0 1 1 1 1 1 1 1 0 1 0 1 0 2 1 1 1 ``` **说明** 在第一个测试用例的第一个测试中，数组 $ [1, 2, 1, 7] $ 是一个 multitest，因为数组 $ [2, 1, 7] $ 是一个 test。数组 $ [2, 1, 7] $ 本身不是一个 multitest，但将第一个数字替换为 $ 1 $ 后，得到数组 $ [1, 1, 7] $，这是一个 multitest。数组 $ [1, 7] $ 也不是一个 multitest，但数组 $ [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 $，因为数组本身不是一个 multitest，但将第二个元素替换为 $