ICPC の競技会場では，参加チームが問題に正答するたびに， その問題に対応する色の風船をひとつ，そのチームに配ります． そこであなたは，さまざまな色の風船を， 全部のチームが全問正解してもいいだけの個数用意しました．しかし， 多くの問題についてはごく少数のチームしか解けませんでした． そこであなたは余った風船を近所の子供たちに配ることにしました．

同じ色の風船をいくつか結んだポールを何本か用意して，左から右に並べます． 子供が来ると，左から順に 3 本のポールからひとつずつ風船を外し，3 色の風船をあげます． 風船がなくなったポールは取り除き， 残るポールが 2 本以下になったら風船配りはおしまいです．

風船をもらえる子供の数はポールの順序によって変わります． 上手にポールを並べたら最大何人の子供が風船をもらえるでしょうか．

右の図は風船の個数が 1, 2, 3, 4, 5 のポール 5 本の並べ方を変えるとどうなるかを示しています． ポールを風船の個数が 1, 2, 3, 4, 5 の順に並べると風船をもらえる子供は 3 人だけですが， 5, 4, 3, 2, 1 の順ならば 5 人の子供がもらえます．

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

n
b₁ b₂ … b_n

n はポールの本数を表す． n は，3 以上 50 以下の整数である． b₁ から b_n は各ポールの風船の数を表す． b_i は，50 以下の正の整数である．

入力の終わりは，ひとつのゼロからなる行で表される． データセットは 50 個以内である．

各データセットについて，最大で何人の子供に風船を配れるかを示す整数を 1 行で出力せよ．

5
1 2 3 4 5
9
1 3 3 3 3 3 3 4 4
4
5 2 8 3
0

5
9
5