Виставка#477

Виставка

0,5 секунди
256 мегабайтів
Середня

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

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

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

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

[, , , , , , ].

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

.

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

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

Оцінювання

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