Емма и странный круг
После победы на одной из самых престижных кинопремий мира, Эмма получила весьма необычный подарок — круг, разделённый на сектора. Всего в круге чётное количество секторов — n. В некоторых секторах находятся камешки, а некоторые остаются пустыми.
Эмма заметила, что она может перемещать камешки только в противоположные сектора. При этом невозможно разместить два камешка в одном секторе (не спрашивайте почему и как, это магия). Поскольку вечеринка после вручения премии оказалась довольно скучной, Эмма решила выяснить, какова длина самой длинной последовательности из секторов, заполненных камешками, которую она может получить после неограниченного количества перемещений камешков.
Эмма — актриса, поэтому ваша задача, как настоящего умника, помочь ей в этом.
Напомним правила перемещения:
Камешек можно перемещать только в противоположный сектор.
В каждом секторе может находиться не более одного камешка.
Для лучшего понимания на рисунке показан один из вариантов перемещения камешков в первом тестовом примере.
Входные данные
В первой строке дано одно целое число n. В следующей строке n чисел 0 или 1 (1 — в секторе находится камешек, 0 — сектор пустой). 1 <= n <= 10^6.n — чётное число. Существует хотя бы один пустой сектор.
Выходные данные
Выведите одно целое число — длину самой длинной магической последовательности.