Dado un arreglo de ~n~ enteros, tu tarea es encontrar la suma máxima de valores en un subarreglo contiguo no vacío.

Entrada

La primera línea de entrada tiene un número entero ~n~: el tamaño del arreglo.

La segunda línea tiene ~n~ enteros ~x_1,x_2,\dots,x_n~: los valores del arreglo.

Salida

Imprime un entero: la suma máxima del subarreglo.

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~.
• ~-10^9 \leq x_i \leq 10^9~.

Ejemplo de Entrada

8
-1 3 -2 5 3 -5 2 2

Ejemplo de Salida

9