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