負の駆逐

研究室合宿でのプログラミングコンテストで出題した問題． 正解したチームは多かったものの， 解答時間が実質一時間しかなかったせいもあり， 残念ながら期待していた解答をしたチームは無かった． 暇な人は是非チャレンジを． 解答は後日ということで．

円周上に 3 個以上の重ならない点がある． それぞれの点は整数値を持っており， すべての点の値の合計はちょうど 1 である． このとき，次のような操作を考える：

ある点に対し，その点が値 k をもつとき， その点の値の正負を入れ替え，隣り合う点の値に k を加える．

たとえば， 円周上に列んでいる点の値が ..., 4, -1, -2, ... であるとき， 真ん中の点に対してこの操作を行うと ..., 3, 1, -3, ... と値が変化する． いま，円周上の点の数とそれらの値がすべて与えられたとき， 上の操作を最低何回繰り返せば円周上の全ての点の値が負でなくなるだろうか． この回数を求めるプログラムを書け． ただし，点の個数は 32 以下，各点の値の絶対値は 2^25 以下と仮定してよい． 入力は一行毎に「[点の個数]: [各点の値]」という形式で与えられるものとし， 各入力に対する最低操作回数を一行毎に出力すること．

入力例

3: -3 6 -2
5: -3 -1 2 -2 5
4: -4 6 -2 1
3: 11 -2 -8


出力例

10
18
15
20