E. Генератор мультитестов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$b_1, b_2, \ldots, b_m$$$ назовём тестом, если $$$b_1 = m - 1$$$.

Массив $$$b_1, b_2, \ldots, b_m$$$ назовём мультитестом, если массив $$$b_2, b_3, \ldots, b_m$$$ можно разбить на $$$b_1$$$ непустых подмассивов так, что каждый из этих подмассивов является тестом. Обратите внимание, что каждый элемент массива должен войти в ровно один подмассив из разбиения, при этом каждый подмассив должен состоять из последовательных элементов исходного массива.

Определим функцию $$$f$$$ от массива $$$b_1, b_2, \ldots, b_m$$$ как минимальное количество операций вида «Заменить любое $$$b_i$$$ на любое целое неотрицательное число $$$x$$$», которое нужно сделать, чтобы массив $$$b_1, b_2, \ldots, b_m$$$ стал мультитестом.

Дан массив $$$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}]$$$. Подчеркнуты подмассивы после разбиения, а два раза подчеркнуты первые элементы в них.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Примеры
Входные данные
3
4
1 2 1 7
7
3 1 3 1 2 1 1
4
2 7 1 1
Выходные данные
0 1 1 
0 1 1 0 1 1 
1 1 1
Входные данные
1
19
3 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1
Выходные данные
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$$$.