Descripción

Dado un arreglo de \(N\) números, tu tarea es encontrar la suma máxima de valores en un subarreglo.

Para este problema, una subarreglo se define como una secuencia no vacía de elementos consecutivos.

Entrada

En la primera línea un entero \(N\) \((1 \leq N \leq 2 \cdot 10^5)\), que corresponde al tamaño del arreglo.

En la segunda línea \(N\) enteros \(x\) \((-10^9 \leq x_i \leq 10^9)\), que corresponden a los valores del arreglo.

Salida

Imprime un entero, la suma máxima de subarreglo.

Ejemplo

Entrada

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

Salida

9

Entrada

1
-1000000000

Salida

-1000000000

Entrada

5
-1 -1 -1 -1 -2

Salida

-1