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

Вхідні дані

Перший рядок містить число n (1 ≤ n ≤ 106). У другому рядку задано члени послідовності, кожен за модулем не більше 1000.

Вихідні дані

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