Гра з вежами

Обмеження: 2 сек., 256 МіБ

Зеник із Марічкою грають у гру з набором веж, розташованих у ряд. Кожна вежа має свою кількість поверхів $h_i$.

На початку гри кулька розташована на першому поверсі однієї з веж. Далі гравець за один хід може:

1. Перенести кульку на 1 поверх вище тієї ж вежі, якщо такий існує.

2. Перенести кульку на той ж поверх сусідньої зліва чи справа вежі, якщо це можливо.

Наприклад, якщо кулька знаходиться на 4 поверсі 7 вежі, то за один хід її можна перенести або на 5 поверх 7 вежі, або на 4 поверх 6 вежі, або на 4 поверх 8 вежі. Кожен з ходів можна зробити лише якщо відповідний поверх існує.

Гравці ходять по черзі, перший хід робить Марічка. Гравець, який не може зробити хід — програє. Якщо за $47^{74}$ ходів переможця не виявлено, то оголошується нічия. Допоможіть Зенику та Марічці визначити для кожної вежі, хто ж переможе, якщо початково кулька знаходиться на 1 поверсі цієї вежі.

Вхідні дані

У першому рядку задано єдине ціле число $n$ — кількість веж.

У другому рядку задано $n$ цілих чисел $h_i$ — висоти веж.

Вихідні дані

Виведіть єдиний рядок з $n$ символів. $i$-ий символ повинен бути 1, якщо перемагає перший гравець (Марічка), 2, якщо другий (Зеник), та 0, якщо гра завершиться нічиєю.

Обмеження

$1 \le n \le 2 \cdot 10^5$,

$1 \le h_i \le 10^9$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 1 2 1	212

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 1 1 1	0000

Примітки

У першому прикладі, якщо гра починається у першій вежі, то перший гравець змушений перенести кульку на 2 вежу, другий гравець переносить кульку на поверх вище і перемагає. Якщо ж гра починається у другій вежі, то перший переносить кульку на поверх вище і перемагає.

У другому прикладі гравці можуть безмежну кількість разів переносити кульку між вежами, тому для усіх початкових веж гра завершиться нічиєю.