B - Pizza 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

ここに円形のピザが 1 枚あります。
高橋くんは長さ N の数列 A を使ってこのピザを以下の手順で切り分けます。

  • 最初に、円の中心から 12 時の方向に切れ込みをひとつ入れます。
  • 次に、以下の操作を N 回繰り返します。 i 回目の操作では以下を行います。
    • まず、ピザを時計回りに A_i 度回転させる。
    • 次に、円の中心から 12 時の方向に切れ込みをひとつ入れる。

例えば、A=(90,180,45,195) として手順を行うと、下図のようになります。

このとき、最も大きなピザの中心角が何度であるか求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 359
  • 1 \le A_i \le 359
  • 同じ場所に複数回切れ込みが入ることはない。

入力

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

N
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

4
90 180 45 195

出力例 1

120

この入力は問題文中の例と一致します。
最も大きなピザの中心角は 120 度です。

入力例 2

1
1

出力例 2

359

入力例 3

10
215 137 320 339 341 41 44 18 241 149

出力例 3

170

Score : 200 points

Problem Statement

We have a circular pizza.
Takahashi will cut this pizza using a sequence A of length N, according to the following procedure.

  • First, make a cut from the center in the 12 o'clock direction.
  • Next, do N operations. The i-th operation is as follows.
    • Rotate the pizza A_i degrees clockwise.
    • Then, make a cut from the center in the 12 o'clock direction.

For example, if A=(90,180,45,195), the procedure cuts the pizza as follows.

Find the center angle of the largest pizza after the procedure.

Constraints

  • All values in input are integers.
  • 1 \le N \le 359
  • 1 \le A_i \le 359
  • There will be no multiple cuts at the same position.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

4
90 180 45 195

Sample Output 1

120

This input coincides with the example in the Problem Statement.
The center angle of the largest pizza is 120 degrees.

Sample Input 2

1
1

Sample Output 2

359

Sample Input 3

10
215 137 320 339 341 41 44 18 241 149

Sample Output 3

170