Зверніть увагу, що у цій задачі вам, можливо, буде корисно використовувати Python 3.10 (PyPy) замість Python 3.13.

За успішне виконання домашнього завдання Козаку Вусу призначили роль організатора щорічної виставки дронів. Для цього Козак Вус придбав ~n~ дронів. Дрон з індексом ~i~ має потужність ~p_i~. Для показу дронів використовується стенд, на якому Козак Вус вже розмістив дрони у порядку індексів ~1, 2, \ldots, n~. Міняти дрони місцями не дозволяється.

На жаль, деякі з дронів (можливо, нуль), які придбав Козак Вус, виявилися підробленими і тому мають від'ємну потужність (~p_i < 0~). Аби не засмучувати публіку, Козак Вус вирішив приховати деякі (можливо, жодні) дрони за завісою.

Завіса працює наступним чином:

• Вона складається з двох однакових частин (лівої та правої) і задається трьома цілими параметрами (~l, r, x~), де:

  • ~l~ — початок лівої частини завіси.

  • ~r~ — кінець правої частини завіси.

  • ~1 \leq l < r \leq n~

  • ~x \geq 1~.

• Лівою частиною завіси Козак Вус заховає перші ~x~ дронів, починаючи з дрона з індексом ~l~. Більш формально, Козак Вус заховає дрони з індексами ~l, l+1, \ldots, l+x-1~.

• Правою частиною завіси Козак Вус заховає останні ~x~ дронів, закінчуючи дроном з індексом ~r~. Більш формально, Козак Вус заховає дрони з індексами ~r-x+1, r-x+2, \ldots, r~.

• Додатково, Козак Вус вирішив, що має виконуватись ~2\cdot x < r-l+1~. Тобто між двома частинами завіси має залишитись принаймні один неприхований дрон.

Потужність виставки визначається як сума потужностей усіх неприхованих дронів.

Допоможіть Козаку Вусу досягти максимальної потужності виставки, якщо дозволяється не більше одного разу скористатися завісою.

Input

Перший рядок містить одне ціле число ~n~ (~2 \leq n \leq 2500~) — довжина масиву ~p~.

Другий рядок містить ~n~ цілих чисел ~p_1, p_2, \ldots, p_n~ (~-10^{9} \leq p_i \leq 10^{9}~) — елементи масиву ~p~, де ~p_i~ — потужність дрона з індексом ~i~.

Output

У єдиному рядку вихідних даних виведіть одне ціле число — максимальну потужність виставки, яку можна досягти.

Sample Input 1

7
3 -1 3 1 -4 -5 1

Sample Output 1

5

Sample Input 2

2
6 7

Sample Output 2

13

Notes

У першому прикладі можна скористатися завісою з параметрами ~((l,r,x)=(1,6,2))~. Завіса ляже наступним чином:

[~\large \color{green}{3}~, ~\large \color{green}{-1}~, ~\large 3~, ~\large 1~, ~\large \color{red}{-4}~, ~\large \color{red}{-5}~, ~\large 1~].

Тут зеленим позначено ліву частину завіси, а червоним — праву частину завіси. Тоді потужність виставки буде обчислюватись наступним чином:

~\color{green}{0}~ ~+~ ~\color{green}{0}~ ~+~ ~3~ ~+~ ~1~ ~+~ ~\color{red}{0}~ ~+~ ~\color{red}{0}~ ~+~ ~1~ ~=~ ~5~.

Зверніть увагу, що Козак Вус не може розмістити завісу з параметрами, наприклад, ~(l,r,x)=(1, 6, 3)~, оскільки тоді між двома частинами завіси не залишиться неприхованого дрона.

У другому прикладі можна не користуватися завісою й отримати максимальну потужність виставки ~6 + 7 = 13~.

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