Нещодавно Козак Вус придбав собі новий телефон, і аби насолодитися новітніми технологіями, він вирішив пограти у популярну гру Stawl Brars. Сенс гри полягає у наступному:

У рядку розташовано ~n~ сейфів, пронумерованих від ~1~ до ~n~ зліва направо. Кожен сейф містить рівно одну з двох кількостей монет: ~1~ або ~2~ золоті монети. Козаку Вусу потрібно здобути якомога більше золотих монет. Для цього він може вибрати підвідрізок ~[l, r]~ (~1 \leq l \leq r \leq n~) на цьому рядку і застосувати на ньому одну з наступних атак:

• Звичайна атака — вибиває рівно ~1~ монету з кожного сейфу на ~[l, r]~. Ця операція завжди дозволена. Кількість здобутих монет дорівнює ~r-l+1~.

• Суператака — вибиває рівно ~2~ монети з кожного сейфу на ~[l, r]~. Операція дозволена лише тоді, коли усі сейфи на підвідрізку ~[l, r]~ містять по ~2~ монети. Кількість здобутих монет дорівнює ~2\cdot(r-l+1)~.

Потрібно вибрати операцію (або не виконувати жодної) та підвідрізок так, щоб загальна кількість здобутих монет була максимальною.

Input

Перший рядок містить одне ціле число ~n~ (~1 \leq n \leq 2 \cdot 10^5~) — довжина рядка.

Другий рядок містить ~n~ цілих чисел ~c_1, c_2, \dots, c_N~ (~1 \leq c_i \leq 2~), де ~c_i~ — кількість золотих монет в ~i~-му сейфі.

Output

Виведіть одне ціле число — максимальну кількість монет, яку може здобути Козак Вус.

Sample Input 1

5
2 1 2 2 2

Sample Output 1

6

Sample Input 2

4
1 1 1 1

Sample Output 2

4

Sample Input 3

6
2 2 1 1 2 2

Sample Output 3

6

Notes

У першому прикладі Козак Вус може вибрати підвідрізок ~[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~ монет.

Ви отримаєте не менше ~10~ балів, якщо ваш розв'язок буде коректно працювати для ~n \leq 100~.

Ви отримаєте не менше ~40~ балів, якщо ваш розв'язок буде коректно працювати для ~n \leq 1000~.