J. Ним Ласкера

На столе $n$ кучек. За ход игрок либо берёт из одной кучки любое положительное число камней, либо разбивает одну кучку на две непустые, ничего не забирая. Проигрывает тот, кто не может сделать ход.

В первой строке $n$ ($1 \le n \le 10^5$). Во второй строке $n$ чисел $a_i$ ($1 \le a_i \le 10^9$).

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