問題文

すぬけくんとアライグマは $N$ 枚のカードの山を作りました。カードの山の上から $i$ 番目のカードには整数 $a_i$ が書かれています。

$N$ 枚のカードを分け合うことにしました。 すぬけくんがカードの山の上から何枚かのカードを取ったあと、アライグマは残ったカード全てを取ります。 このとき、すぬけくんもアライグマも $1$ 枚以上のカードを取る必要があります。

すぬけくんとアライグマが持っているカードに書かれた数の総和をそれぞれ $x,y$ として、$|x-y|$ を最小化したいです。 $|x-y|$ としてありうる値の最小値を求めなさい。

制約

• $2 \\leq N \\leq 2 \\times 10^5$
• $\-10^{9} \\leq a_i \\leq 10^{9}$
• $a_i$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $a_2$ $...$ $a_{N}$

出力

答えを出力せよ。

入力例 1

6
1 2 3 4 5 6

出力例 1

1

すぬけくんが上から $4$ 枚のカードを、アライグマが残った $2$ 枚のカードを取ったとき、$x=10,y=11$ となって、$|x-y|$ は $1$ となり、これが最小です。

入力例 2

2
10 -10

出力例 2

20

すぬけくんは上から $1$ 枚のカードを、アライグマは残った $1$ 枚を取るしかありえません。このとき $x=10,y=-10$ となって、$|x-y|$ は $20$ となります。