Дана последовательность целых чисел длины n. Найдите в ней непустую подпоследовательность подряд идущих чисел, такую, что сумма чисел в ней максимальна.

Входные данные

Число n (1 ≤ n ≤ 106) в первой строке. Во второй строке заданы члены последовательности, каждый по модулю не больше 1000.

Выходные данные

Выведите максимальную сумму чисел в непустой подпоследовательности подряд идущих чисел.