Емма та дивне коло#10222
Після перемоги на одній із найпрестижніших кінопремій світу Емма отримала досить незвичайний подарунок — коло, поділене на сектори. Коло має парну кількість секторів, яку позначимо як . У деяких секторах лежать камінці, а деякі сектори порожні.
Емма помітила, що може пересувати камінець лише у протилежний сектор. Однак неможливо розмістити два камінці в одному секторі (не питайте чому і як — це магія). Оскільки вечірка після вручення премії виявилася досить нудною, Емма вирішила з'ясувати, якою може бути довжина найдовшої послідовності підряд секторів, заповнених камінцями, яку вона зможе отримати після будь-якої кількості переміщень.
Емма — акторка, тому ваше завдання — допомогти їй у цій магічній головоломці.
Нагадаємо правила переміщення камінців:
Камінець можна пересунути лише у протилежний сектор.
У секторі не може бути більше одного камінця.
Для кращого розуміння на малюнку зображено один із варіантів переміщення камінців у першому прикладі.
У першому рядку міститься одне ціле число . У другому рядку — чисел: або ( означає, що в секторі є камінець, — сектор порожній). 1 \leq n \leq 10^6. — парне число. Існує хоча б один порожній сектор.
Виведіть одне ціле число — довжину найдовшої магічної послідовності (підряд заповнених секторів), яку можна отримати.
Приклад 1
Приклад 2