Jaś znalazł w domu długą taśmę. Bez chwili namysłu napisał na taśmie pewien ciąg liczb całkowitych. Teraz chciałby przeciąć taśmę w pewnym miejscu tak, aby różnica pomiędzy sumą liczb na jednym kawałku a sumą liczb na drugim kawałku była jak najbliższa zeru (na jednym kawałku musi się znajdować co najmnniej jedna liczba). Chcielibyśmy znać wartość bezwzględną z owej różnicy.

입력 형식

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (2 ≤ n ≤ 10⁶), oznaczającą ilość liczb wypisanych na taśmie. Drugi wiersz zawiera n liczb całkowitych a_i (-10³ ≤ a_i ≤ 10³), oznaczających kolejne liczby wypisane na taśmie.

출력 형식

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnej wartości bezwględnej różnicy pomiędzy dwoma kawałkami.

예제 입력

6
1 2 3 4 5 6

예제 출력

1

힌트

 </p>

Jaś może przeciąć taśmę po czwartej liczbie 1, 2, 3, 4|5, 6, czyli wartość bezwględna z różnicy pomiędzy dwoma kawałkami wynosi |(1 + 2 + 3 + 4) - (5 + 6)| = 1.