004 - 部員の変遷

問題

春は別れと出会いの季節．今年もまた，伝統ある情報処理部の歴史に新たな名前を刻むときが来た．

部活日誌には，この部活の n 年分の部員の推移が記録されている．記録によれば，初年度より前の部員数はもちろん 0 人であり，毎年部員は 4 月に新入生のみが入部しており，3 年後の 3 月に卒業するタイミングでのみ退部しているようだ．

部の変遷を紐解くために， n 年間の各年の新入部員の数のデータから在籍する部員の数が最大になった年度の部員数を調べてみよう．

Input

入力は複数のデータセットからなる．データセットの個数は 50 を超えない．各データセットは次の形式で表される．

n
a1 a2 … an

n は新入部員の数が記録されている年数を表す， 3 以上 1000 以下の整数である．続く行は各年度の新入部員の数を表す n 個の整数からなり， i 年目の新入部員の数 a _i はそれぞれ 0 ≤ a _i ≤ 10 ⁸ を満たす．

入力の終わりは，ゼロ 1 つだけからなる行で表される．

Output

各データセットについて，在籍する部員の数が最大になった年度の部員数を 1 行に出力せよ．

Sample Input

8
5 2 3 4 8 2 1 6
3
2 1 7
5
0 1 3 3 3
5
0 0 0 0 0
0

Sample Output

15
10
9
0