N+1

0

N

0

N

i

i

i+1

d_i

0

N

N
d_{0}
d_{1}
:
d_{N-1}

• 入力は $N+1$ 行からなる。
• $1$ 行目には点の番号の最大を表す整数 $N(1≦N≦500)$ が与えられる。
• $2$ 行目から $N+1$行目までの $i+2$ 行目 $(0 ≦ i < N)$には、$i$ 番と $i+1$ 番の点の距離を表す整数 $d_i(1≦d_i≦30,000)$ が与えられる。

2

1

0

N

2

0

N

10^{-3}

1
1024

1024
1024

• 入力より $0$ 番の点と $1$ 番の点があり、それらの間の距離は $1024$ であることが分かります。
• 求める距離は、$0$ 番の点と $1$ 番の点の間の距離なので最大値も最小値もともに $1024$ です。

3
3
4
5

12
0

• $0$ 番の点と $3$ 番の点の間の距離が最も大きくなるのは、下図(a)のように $0$ 番の点と $3$ 番の点を端にして $4$ 点が一直線に並ぶ場合で、その距離は $3+4+5=12$ となります。
• $0$ 番の点と $3$ 番の点の間の距離が最も小さくなるのは、下図(b)のように $0$ 番の点と $3$ 番の点の位置が等しい場合で、その距離は $0$ となります。

2
512
512

1024
0

• $0$ 番の点と $2$ 番の点の間の距離が最も大きくなるのは、下図(a)のように $0$ 番の点と $2$ 番の点を端にして $3$ 点が一直線に並ぶ場合で、その距離は $512+512=1024$ となります。
• $0$ 番の点と $2$ 番の点の間の距離が最も小さくなるのは、下図(b)のように $0$ 番の点と $2$ 番の点の位置が等しい場合で、その距離は $0$ となります。

3
4
8
1

13
3

• $0$ 番の点と $3$ 番の点の間の距離が最も大きくなるのは、下図(a)のように $0$ 番の点と $3$ 番の点を端にして $4$ 点が一直線に並ぶ場合で、その距離は $4+8+1=13$ となります。
• $0$ 番の点と $3$ 番の点は重なることができないので、$0$ 番の点と $3$ 番の点の間の距離が最も小さくなるのは下図(b)のように $1$ 番の点と $2$ 番の点を繋ぐ線分上に $0$ 番の点と $3$ 番の点がある場合で、その距離は $8-4-1=3$ となります。

10
1
2
3
4
5
6
7
8
9
10

55
0

• $0$ 番の点と $10$ 番の点の間の距離が最も大きくなるのは、$0$ 番の点から $10$ 番の点が順に一直線に並ぶ場合で、その距離は $1+2+3+4+5+6+7+8+9+10=55$ となります。
• $0$ 番の点と $10$ 番の点の間の距離が最も小さくなる一例は、$0$ 番の点から $10$ 番の点まで順に円型に並び、$0$ 番の点と $10$ 番の点の位置が等しくなった場合です。

1
1024

1024
1024

3
3
4
5

12
0

2
512
512

1024
0

3
4
8
1

13
3

10
1
2
3
4
5
6
7
8
9
10

55
0