D. Menor soma de intervalo

Time limit: 2000 msMemory limit: 256 MB

Você recebe uma lista de $N$ inteiros $A_1,A_2,\ldots,A_N$ .

Escolha um intervalo contíguo não vazio da lista e calcule o valor absoluto da soma de seus elementos. Encontre o menor valor que pode ser obtido.

Formalmente, encontre $\min_{1 \le L \le R \le N}\left|\sum_{i=L}^{R} A_i\right|.$

Input

A primeira linha contém um inteiro $N$ ( $1 \le N \le 2 \times 10^5$ ).

A segunda linha contém $N$ inteiros ().

Output

Imprima um inteiro: o menor valor absoluto da soma de um intervalo contíguo não vazio.

Samples

Sample 1

Input

4
8 -5 -2 6

Output

O intervalo do índice $1$ ao índice $3$ tem soma $8-5-2=1$ . Nenhum intervalo não vazio tem soma $0$ , portanto a resposta é .

D. Menor soma de intervalo

Input

Output

Samples

Sample 1

Sample 2

Sample 3

Sample 4