M - Distance on the Line Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

数直線上に 1 から N までの番号がついた N 個の点があります。N 個の点は次の条件を満たします。

  • 点 i と点 i+1 の距離は d_i である。(1 \leq i \leq N - 1)

このとき、点 1 と点 N の距離としてあり得る最小値を求めてください。

制約

  • 2 \leq N \leq 1000
  • 1 \leq d_i \leq 2000
  • 入力される値はすべて整数

入力

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

N
d_1 d_2 \dots d_{N-1}

出力

答えを出力せよ。

入力例 1

4
5 2 4

出力例 1

1

点 i が存在している地点の座標を x_i とします。例えば (x_1,x_2,x_3,x_4)=(0,-5,-3,1) は条件を満たして、このとき点 1 と点 4 の距離は 1 です。

入力例 2

10
314 159 265 358 979 323 846 264 338

出力例 2

2

Problem Statement

There are N points on a number line, numbered from 1 to N. The N points satisfy the following condition:

  • The distance between point i and point i+1 is d_i. (1 \leq i \leq N - 1)

Find the minimum possible distance between point 1 and point N.

Constraints

  • 2 \leq N \leq 1000
  • 1 \leq d_i \leq 2000
  • All input values are integers.

Input

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

N
d_1 d_2 \dots d_{N-1}

Output

Print the answer.

Sample Input 1

4
5 2 4

Sample Output 1

1

Let x_i be the coordinate of the point i. For example, (x_1,x_2,x_3,x_4)=(0,-5,-3,1) satisfies the condition, and in this case, the distance between point 1 and point 4 is 1.

Sample Input 2

10
314 159 265 358 979 323 846 264 338

Sample Output 2

2