E - Transporting Luggage Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君と青木君は、N 個の荷物を 2 人で手分けして運ぶことになりました。

荷物には 1 から N までの番号が付けられており、荷物 i の重さは A_i です。

2 人は、N 個の荷物のすべてについて、高橋君または青木君のどちらかちょうど一人が運ぶように荷物を分けます。ただし、2 人ともそれぞれ少なくとも 1 つの荷物を運ぶ必要があります。

高橋君が運ぶ荷物の重さの合計を X、青木君が運ぶ荷物の重さの合計を Y とするとき、その差の絶対値 |X - Y| としてあり得る最小値を求めてください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^5 (1 \leq i \leq N)
  • \displaystyle \sum_{i=1}^{N} A_i \leq 10^5
  • 入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを 1 行に出力してください。


入力例 1

3
1 2 4

出力例 1

1

入力例 2

4
1 2 3 6

出力例 2

0

入力例 3

8
15 22 37 41 53 64 78 90

出力例 3

2

入力例 4

20
123 456 789 101 112 131 415 161 718 192 202 212 222 324 252 627 282 930 313 233

出力例 4

1

入力例 5

2
1 99999

出力例 5

99998

Score : 433 pts

Problem Statement

Takahashi and Aoki have decided to share the work of carrying N packages.

The packages are numbered 1 through N, and the weight of package i is A_i.

They will divide the packages so that each of the N packages is carried by exactly one of Takahashi or Aoki. However, both of them must carry at least one package.

Let X be the total weight of the packages carried by Takahashi, and Y be the total weight of the packages carried by Aoki. Find the minimum possible value of the absolute difference |X - Y|.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^5 (1 \leq i \leq N)
  • \displaystyle \sum_{i=1}^{N} A_i \leq 10^5
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer in a single line.


Sample Input 1

3
1 2 4

Sample Output 1

1

Sample Input 2

4
1 2 3 6

Sample Output 2

0

Sample Input 3

8
15 22 37 41 53 64 78 90

Sample Output 3

2

Sample Input 4

20
123 456 789 101 112 131 415 161 718 192 202 212 222 324 252 627 282 930 313 233

Sample Output 4

1

Sample Input 5

2
1 99999

Sample Output 5

99998