Мобільна гра#475

Мобільна гра

0.5 seconds
256 megabytes
Very easy

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

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

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

Input

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

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

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

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

Scoring

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

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