巡回勇者問題

English text is not available in this practice contest.

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

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

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

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

Input

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

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 個以内である.

Output

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

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

Sample Input

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

Output for the Sample Input

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