Виставка#477

Виставка

0.5 seconds
256 megabytes
Medium

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

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

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

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

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

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

Input

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

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

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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

[, , , , , , ].

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

.

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

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

Scoring

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