Нещодавно Козак Вус придбав собі новий телефон, і аби насолодитися новітніми технологіями, він вирішив пограти у популярну гру Stawl Brars. Сенс гри полягає у наступному:
У рядок розташовано сейфів, пронумерованих від до зліва направо. Кожен сейф містить рівно одну з двох кількостей монет: або золоті монети. Козаку Вусу потрібно здобути якомога більше золотих монет. Для цього він може вибрати підвідрізок [l, r] (1 \leq l \leq r \leq n) на цьому рядку і застосувати на ньому одну з наступних атак:
Звичайна атака — вибиває рівно монету з кожного сейфу на [l, r]. Ця операція завжди дозволена. Кількість здобутих монет дорівнює r-l+1.
Суператака — вибиває рівно монети з кожного сейфу на [l, r]. Операція дозволена лише тоді, коли усі сейфи на підвідрізку [l, r] містять по монети. Кількість здобутих монет дорівнює 2\cdot(r-l+1).
Потрібно вибрати операцію (або не виконувати жодної) та підвідрізок так, щоб загальна кількість здобутих монет була максимальною.
Перший рядок містить одне ціле число (1 \leq n \leq 2 \cdot 10^5) — довжина рядка.
Другий рядок містить цілих чисел c_1, c_2, \dots, c_N (1 \leq c_i \leq 2), де c_i — кількість золотих монет в -му сейфі.
Виведіть одне ціле число — максимальну кількість монет, яку може здобути Козак Вус.
Example 1
Example 2
Example 3
У першому прикладі Козак Вус може вибрати підвідрізок [l, r]=[3,5] і застосувати суператаку. В результаті цього він здобуває 2\cdot(5-3+1)=6 монет.
У другому прикладі Козак Вус може вибрати підвідрізок [l, r]=[1,4] і застосувати звичайну атаку. В результаті цього він здобуває (4-1+1)=4 монети.
У третьому прикладі Козак Вус може вибрати підвідрізок [l, r]=[1,6] і застосувати звичайну атаку. В результаті цього він здобуває (6-1+1)=6 монет.
Ви отримаєте не менше балів, якщо ваш розв'язок буде коректно працювати для n \leq 100.
Ви отримаєте не менше балів, якщо ваш розв'язок буде коректно працювати для n \leq 1000.