O. Игра Гранди

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

Кучка из одного или двух камней ходов не даёт: единицу разбить нельзя, а двойку — только на равные части.

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

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