Самый убыточный отрезок

Найдите наименьшую сумму непустого куска из подряд идущих элементов.

В первой строке число $n$ от $1$ до $10^6$. Во второй — $n$ чисел от $-10^9$ до $10^9$.

Одно число.