如果 $$$b_1 = m - 1$$$,我们将数组 $$$b_1, b_2, \ldots, b_m$$$ 称为测试。
如果数组 $$$b_2, b_3, \ldots, b_m$$$ 可以拆分为 $$$b_1$$$ 非空子数组,这样每个子数组都是一个测试,那么我们将数组 $$$b_1, b_2, \ldots, b_m$$$ 称为多重测试。请注意,数组的每个元素必须恰好包含在一个子数组中,并且子数组必须由连续的元素组成。
让我们将数组 $$$b_1, b_2, \ldots, b_m$$$ 中的函数 $$$f$$$ 定义为“将任何 $$$b_i$$$ 替换为任何非负整数 $$$x$$$”形式的最小操作数,需要执行此操作,以便数组 $$$b_1, b_2, \ldots, b_m$$$变成多重测试。
给定一个正整数数组 $$$a_1, a_2, \ldots, a_n$$$。对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$i$$$,找到 $$$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]$$$, $$$[\下划线{7}, 1, 2, 3, 4, 5, 6, 7]$$$, $$$[\下划线{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}]$$$。下划线是分割后的子数组,双下划线是每个子数组的第一个元素。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 数字 - $$$f([a_i, a_{i+1}, \ldots, a_n])$$$,每个 $$$i$$$ 从 $$$1$$$ 到 $$$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
注意
在第一个测试的第一个测试用例中,数组 $$$[1, 2, 1, 7]$$$ 是多重测试,因为数组 $$$[2, 1, 7]$$$ 是一个测试。数组$$$[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$$$。