K. Кайлес

Перед игроками стоят несколько рядов кеглей. За ход игрок сбивает одну кеглю или две соседние в каком-нибудь ряду; ряд при этом распадается на два (возможно, пустых). Проигрывает тот, кто не может сделать ход.

В первой строке $n$ ($1 \le n \le 10^5$) — количество рядов. Во второй строке $n$ чисел $a_i$ ($0 \le a_i \le 10^{18}$) — длины рядов.

Выведите $1$, если выигрывает первый игрок, и $2$ иначе.