시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB76685.714%

문제

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

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

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

  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$, \ldots, $b_n$ --- элементы полученного Загадочником массива $b$ ($|b_i| \leqslant 10^9$).

출력

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

예제 입력 1

3
-2 0 2

예제 출력 1

1 1

예제 입력 2

6
-1 2 -3 -4 4 2

예제 출력 2

1 1 0 1 1

예제 입력 3

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

예제 출력 3

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$ в принципе не мог быть получен описанным в условии образом.