Стіна

Задача: Пошук найменшої суми

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

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

Вхідні дані

• Перше число $n$ ($1\le n\le 10^5$) — кількість елементів у масиві $A$.

• Другий рядок містить $n$ цілих чисел $A[i]$ ($-10^4\le A[i]\le 10^4$) — елементи масиву.

Вихідні дані

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

Приклад:

Вхід:

5
3 -1 -4 2 5

Вихід:

-5

Примітка:

У наведеному прикладі найменша сума підмасиву досягається підмасивом $[-1,-4]$, сума якого дорівнює $-5$.

Приклади