Після перемоги на одній з найвідоміших кінопремій світу Емма отримала дуже дивний подарунок - коло розбите на сектори. Всього коло має парну кулькусть секторів - n. У деяких секторах лежить камінець, деякі сектори пусті.

Емма побачила, що вона може перекладати камінці тільки в протилежний сектор. При цьому неможливо розмістити два камінці в одному секторі (не питайте чому і як, це магія). Так як вечірка після після вручення кінопремії доволі нудна, дівчинка захотіла дізнатись -- яка довжина найдовшої послідовності з секторів заповненими камінцями вона може отримати після необмеженої кількості перекладань камінців.

Емма -- акторка, тому ваша задача як справжнього розумника допомогти їй в цьому.

Нагадаємо правила перекладань:

• Камінець можна перекладати тільки в протилежний сектор.
• В кожному секторі не більше одного камінця.

Для кращого розуміння на малюнку зображено один з варіантів перекладання камінців в першому тестовому прикладі.

Вхідні дані

У першому рядку одне ціле число n. У наступному рядку n чисел 0 або 1 (1 - в секторі лежить камінець, 0 - сектор пустий). 1 <= n <= 106. n - парне число. Існує хоча б один пустий сектор.

Вихідні дані

Одне ціле число, відповідь до задачі - довжина найдовшої магічної послідовності.