Вам дано масив цілих чисел розміру . Ваше завдання — знайти найменшу можливу суму, яку можна отримати, вибравши підмасив з .
Підмасив — це неперервна частина масиву. Наприклад, якщо 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
Приклад 2