Загадочник похищает окружного прокурора Джила Колсона.
Чтобы спастись, Колсон должен отгадать три загадки. Бэтмен помогает ему отгадать первые две, но третья загадка оказалась слишком сложной. Сможете ли вы помочь ему с отгадкой?
Загадка устроена следующим образом:
Требуется по данному массиву $$$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$$$ в принципе не мог быть получен описанным в условии образом.