B. Человек-паук
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Питер Паркер планирует сыграть с Доктором Октопусом в игру о циклах. Циклом называется последовательность вершин, такая что первая вершина соединена со второй, вторая — с третьей и так далее, а последняя, в свою очередь, соединена с первой. Цикл может состоять и из одной изолированной вершины.

В начале игры имеются k циклов, i-й из которых состоит ровно из vi вершин. Игроки ходят по очереди, Питер ходит первым. За один ход игрок должен выбрать какой-нибудь цикл, состоящий хотя бы из 2 вершин (обозначим размер выбранного цикла за x), и заменить его двумя непустыми циклами размера p и x - p для некоторого 1 ≤ p < x, выбор которого остаётся на усмотрение игрока. Игрок, который не может сделать ход, проигрывает (и расстаётся с жизнью!).

Питер хочет протестировать несколько изначальных конфигураций игры, перед тем как вступить в схватку с Доктором Октопусом. Изначально набор циклов пуст. Перед i-м тестом Питер добавляет в набор цикл, состоящий из ai вершин (обратите внимание: набор является мультимножеством, то есть может содержать несколько циклов одинакового размера). После добавления каждого цикла Питер хочет знать, кто выигрывает на текущем наборе?

Питер вообще неплохо разбирается в математике, но сейчас решил обратиться к вам за помощью.

Входные данные

В первой строке входных данных записано целое число n (1 ≤ n ≤ 100 000) — количество тестов, которые собирается провести Питер.

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109), i-е из которых равно количеству вершин в цикле, добавленном перед i-м тестом.

Выходные данные

Выведите результаты всех тестов в порядке, в котором они проводятся. Выводите 1, если при оптимальной игре победит игрок, который ходит первым, и 2 в противном случае.

Примеры
Входные данные
3
1 2 3
Выходные данные
2
1
1
Входные данные
5
1 1 5 1 1
Выходные данные
2
2
2
2
2
Примечание

Рассмотрим первый пример:

В первом тесте Питера есть только один цикл, состоящий из 1 вершины, поэтому первый игрок не может сделать ход и проигрывает.

Во втором тесте есть один цикл длины 1 и один цикл длины 2. Первый игрок делит второй цикл на два цикла длины 1, после чего второй игрок не может сделать ход и проигрывает.

В третьем тесте имеются циклы размера 1, 2 и 3. Первый игрок может поделить последний цикл на циклы длины 1 и 2, после чего останется набор 1, 1, 2, 2, в котором можно сделать ровно два хода — делить циклы длины 2 на два цикла длины 1. Таким образом, оба игрока сделают по одному ходу, и второй проиграет.

Рассмотрим второй тестовый пример:

Циклы длины 1 бесполезны, потому что с ними никогда нельзя сделать ход, поэтому можно считать, что их просто нет.

Когда появляется цикл длины 5, у первого игрока есть два варианта хода: поделить его на 1 и 4 или на 2 и 3.

  • Если поделить на циклы длины 1 и 4, то своим ходом второй игрок поделит 4 на два цикла длины 2, после чего останется два однозначно определяемых хода.
  • Если поделить на циклы длины 2 и 3, то второй игрок поделит цикл длины 3 на 2 и 1, опять оставив ситуацию когда есть два однозначных хода.

Таким образом, второй игрок может гарантировать себе победу во всех тестах второго примера.