Гра з вежами

Обмеження: 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 вежу, другий гравець переносить кульку на поверх вище і перемагає. Якщо ж гра починається у другій вежі, то перший переносить кульку на поверх вище і перемагає.

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