409520: GYM103608 C Спасительная загадка

C. Спасительная загадкаограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Загадочник похищает окружного прокурора Джила Колсона.

Чтобы спастись, Колсон должен отгадать три загадки. Бэтмен помогает ему отгадать первые две, но третья загадка оказалась слишком сложной. Сможете ли вы помочь ему с отгадкой?

Загадка устроена следующим образом:

1. Загадочник записал и спрятал массив целых чисел $$$a$$$ длины $$$n$$$.
2. Затем он циклически сдвинул его на какую-то величину $$$x$$$ влево, после чего полученный сдвиг поэлементно вычел из исходного массива.
3. Полученный в результате массив $$$$$$b = [a_1 - a_{x+1}, a_2 - a_{x+2}, \ldots, a_{n} - a_{x}]$$$$$$ (иными словами, массив, в котором $$$b_i = a_i - a_{(i + x) \bmod n}$$$ для всех $$$i$$$), Загадочник сообщил Колсону.

Требуется по данному массиву $$$b$$$ восстановить все возможные величины сдвига $$$x$$$, которые могли привести к получению такого массива $$$b$$$ из какого-то массива $$$a$$$.

Входные данные

В первой строке ввода дано единственное целое число $$$n$$$ — длина исходного массива ($$$1 \leqslant n \leqslant 10^6$$$).

Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ — элементы полученного Загадочником массива $$$b$$$ ($$$|b_i| \leqslant 10^9$$$).

Выходные данные

Выведите через пробел $$$n - 1$$$ целое число, $$$i$$$-е из которых равно $$$1$$$, если $$$x = i$$$ могло иметь место, и $$$0$$$ иначе.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

Подзадача	Баллы	Дополнительные ограничения	Необходимые подзадачи	Информация о проверке
1	7	$$$n \leqslant 5$$$, $$$|b_i| \leqslant 10$$$ для всех $$$i$$$	–	полная
2	8	$$$n \in \mathbb{P}$$$ (простое)	–	полная
3	13	$$$n = 2^k$$$ для некоторого целого $$$k$$$	–	полная
4	14	количество $$$i$$$, для которых $$$b_i \neq 0$$$, не более десяти	1	полная
5	15	$$$n \leqslant 1000$$$	1	полная
6	23	$$$n \leqslant 10^5$$$	5	первая ошибка
7	20	нет	1 – 6	первая ошибка

ПримерыВходные данные

3
-2 0 2

Выходные данные

1 1 

Входные данные

6
-1 2 -3 -4 4 2

Выходные данные

1 1 0 1 1 

Входные данные

7
-1 1 -1 1 -1 1 -1

Выходные данные

0 0 0 0 0 0 

Примечание

В первом примере такой массив $$$b$$$ мог быть получен, например, из массива $$$a = [2, 4, 4]$$$ сдвигом на $$$1$$$ влево или из массива $$$a = [2, 2, 4]$$$ сдвигом на $$$2$$$ влево.

В первом примере данный массив $$$b$$$ ни при каком $$$a$$$ не мог быть получен сдвигом на $$$3$$$, а для сдвигов $$$1$$$ или $$$4$$$, например, подошли бы массивы $$$a = [1, 2, 0, 3, 7, 3]$$$ и $$$a = [3, 7, 0, 3, 4, 5]$$$, соответственно.

Для третьего примера можно показать, что такой $$$b$$$ в принципе не мог быть получен описанным в условии образом.