시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 1024 MB2000.000%

문제

あなたは 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) をスペース区切りで出力する.

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

예제 입력 1

4
2 3 4
4
2 -3 4
6
-1 -1 -1 -1 -1
6
-1 -1 100 -1 -1
0

예제 출력 1

21
2 4 1 3
9
2 1 4 3
-5
1 2 3 4 5 6
492
1 4 3 5 2 6