Стіна#10958

Стіна

0,8 секунди
256 мегабайтів
Легка

Вам дано масив цілих чисел розміру . Ваше завдання — знайти найменшу можливу суму, яку можна отримати, вибравши підмасив з .

Підмасив — це неперервна частина масиву. Наприклад, якщо A = [3, -1, -4, 2, 5], то є підмасивом, а [3, 2, 5] — ні.

Вхідні дані

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

Другий рядок містить цілих чисел A_i (-10^4 \leq A_i \leq 10^4) — елементи масиву.

Вихідні дані

Виведіть одне число — найменшу можливу суму підмасиву.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading