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 個の街すべてでクエストが発生しているため,勇者であるあなたは冒険に出かけることにした.冒険は以下を満たすものでなければならない.
冒険が終了した後の所持金をできるだけ多くするには,どのような順番でクエストを行えばよいだろうか?
入力は複数のデータセットからなる.各データセットは次の形式で表される.
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) をスペース区切りで出力する.
答えとしてあり得るものが複数ある場合は,どれを出力しても正解となる.
4 2 3 4 4 2 -3 4 6 -1 -1 -1 -1 -1 6 -1 -1 100 -1 -1 0
21 2 4 1 3 9 2 1 4 3 -5 1 2 3 4 5 6 492 1 4 3 5 2 6