Массив \(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}]\). Подчеркнуты подмассивы после разбиения, а два раза подчеркнуты первые элементы в них.
Выходные данные
Для каждого набора входных данных выведите \(n - 1\) число — значения \(f([a_i, a_{i+1}, \ldots, a_n])\) для каждого \(i\) от \(1\) до \(n - 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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
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
|