AtCoder Regular Contest 078

C - Splitting Pile


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 300

問題文

すぬけくんとアライグマは 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 となります。

Score : 300 points

Problem Statement

Snuke and Raccoon have a heap of N cards. The i-th card from the top has the integer a_i written on it.

They will share these cards. First, Snuke will take some number of cards from the top of the heap, then Raccoon will take all the remaining cards. Here, both Snuke and Raccoon have to take at least one card.

Let the sum of the integers on Snuke's cards and Raccoon's cards be x and y, respectively. They would like to minimize |x-y|. Find the minimum possible value of |x-y|.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • -10^{9} \leq a_i \leq 10^{9}
  • a_i is an integer.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{N}

Output

Print the answer.


Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

1

If Snuke takes four cards from the top, and Raccoon takes the remaining two cards, x=10, y=11, and thus |x-y|=1. This is the minimum possible value.


Sample Input 2

2
10 -10

Sample Output 2

20

Snuke can only take one card from the top, and Raccoon can only take the remaining one card. In this case, x=10, y=-10, and thus |x-y|=20.


Submit提出する