巡回勇者問題

あなたは JAG 王国の勇者である．鍛錬を積んでいるあなたの現在の所持金は 10100 である．

JAG 王国には 1, 2, ..., N で番号付けされた N 個の街がある．また，街 i と街 i+1 (1 ≤ i < N) の間には道路があり，通行すると所持金が Ci 変動する．つまり，Ci が正のときはあなたの所持金が |Ci| だけ増加するが，そうでないときはあなたの所持金が |Ci| だけ減少する．

N 個の街すべてでクエストが発生しているため，勇者であるあなたは冒険に出かけることにした．冒険は以下を満たすものでなければならない．

• 冒険では，N 個すべての街で 1 度ずつクエストを行わなければならない．
• クエストを行う街の順番を (x1, x2, ..., xN) と定めたとする (i ≠ j ならば xi ≠ xj)．あなたは街 x1 を出発地としてクエストを順番に行う．街 xk から xk+1 (1 ≤ k < N) へ移動するときは，xk から xk+1 まで最短経路で移動しなければならない．ここで「最短経路」とは，通る道路の数が最も少ない経路を指す．
• 街 xN で最後のクエストを行うと，そこで冒険は終了となる．

冒険が終了した後の所持金をできるだけ多くするには，どのような順番でクエストを行えばよいだろうか？

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

N

C1 C2 ... CN-1

各データセットは 2 行からなる．最初の行には街の数を表す整数 N (2 ≤ N ≤ 3,000) がある．次の行には空白で区切られた N-1 個の整数 C1, C2, ..., CN-1 がある．Ci は街 i と街 i+1 の間を通行したときに所持金がいくら変動するかを表す値である．ここで C1 から CN-1 はすべて -109 以上 109 以下である．

入力の終わりはゼロひとつを含む行で示す．データセットは 50 個以内である．

各テストケースに対する出力は 2 行からなる．1 行目では，冒険が終了した後の所持金と，冒険を行う前の所持金との差としてあり得る最大値を出力する．2 行目では，その所持金を達成できるような，クエストを行う街の順番 (x1, x2, ..., xN) をスペース区切りで出力する．

答えとしてあり得るものが複数ある場合は，どれを出力しても正解となる．