Задача №1800. Голосование
В некогда прославившейся своей политической стабильностью республике Варении прошла череда революций, в результате чего парламент этой страны и система принятия законов в нём приобрели довольно странную форму.
Парламент Варении состоит из нескольких палат, пронумерованных натуральными числами от 1 до \(10^9\) (палаты с некоторыми номерами могут отсутствовать). Принятие законов происходит следующим образом: сначала каждый депутат голосует за или против принимаемого закона, затем считается число \(K\) — количество палат парламента, в которых голосование признано действительным (голосование может быть признано недействительным в том и только том случае, если количество проголосовавших «за» равно количеству проголосовавших «против»). Далее, чтобы принять итоговое решение о принятии закона, применяется новейшая электронная система: она случайным образом выбирает числа \(A\) и \(B\), а затем сравнивает \(A\)/\(K\) и \(B\).
В очередной раз парламенту Варении предстоит решить судьбу нового закона, предложенного премьер-министром. Однако политические взгляды различных ветвей власти Варении практически противоположны, поэтому все депутаты считают принятие этого закона неприемлемым. Но по своему опыту депутаты знают, что даже если они все проголосуют против, система (не без помощи премьер-министра) может подобрать числа \(A\) и \(B\) таким образом, чтобы закон всё равно оказался принят. Поэтому единственный способ отложить принятие нежелательного закона — это вызвать сбой в системе. Для этого достаточно, чтобы во всех палатах был достигнут ничейный результат голосования: тогда K будет равно нулю, система попытается разделить на ноль, и ещё целый месяц лучшие программисты Варении будут восстанавливать работу электронной системы голосования.
Однако может так получиться, что в одной из палат число депутатов нечётно, поэтому ничья в данной палате невозможна. На этот случай депутаты недавно приняли закон, по которому спикер парламента (не принадлежащий ни одной из палат) может отдать свой голос одной из палат. Поэтому вызвать сбой в системе всегда возможно, если существует не более одной палаты с нечётным количеством депутатов.
По информации о составе палат найдите палату, которой спикер должен отдать свой голос (если это необходимо).
В первой строке входного файла содержится единственное целое число N — количество депутатов в парламенте без учёта спикера (1 \(\le\) \(N\) \(\le\) 800000). В следующей строке содержится \(N\) целых чисел \(c_i\) — номер палаты, в состав которой входит депутат с номером \(i\) (1 \(\le\) \(c_i\) \(\le\) \(10^9\)).
Выведите единственное натуральное число — номер палаты, которой спикер должен отдать свой дополнительный голос, или 0, если голос спикера не потребуется.
Гарантируется, что решение существует.