[ARC092E] Both Sides Merger

给你一个长度为 n (2≤n≤1000) 的序列 a |ai|<=1e9 。可以选择以下操作： 1.选择一个端点的数，删除 2.选择一个非端点的数，将其变为相邻左右两数之和，删去左右两边的数。 若干次操作后序列只剩下一个数，要求结果尽可能大。求每次选数方案。

[problemUrl]: https://atcoder.jp/contests/arc092/tasks/arc092_c あなたは，長さ $ N $ の数列 $ a_1,\ a_2,\ ...,\ a_N $ を持っています。 あなたは，この数列の長さが $ 1 $ になるまで，繰り返し以下の操作を行います。 - まず，数列の要素を $ 1 $ つ選ぶ。 - もしその要素が数列の端だった場合，その要素を削除する。 - もしその要素が数列の端でない場合，その要素を，選んだ要素の両隣の要素の和に書き換える。そしてその後，両隣の要素を削除する。 あなたは，最終的な数列の要素の値を最大化したいです。 最終的な数列の要素の値の最大値と，それを達成する手順を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

- $ 1 $ 行目には，最終的な数列の要素の値の最大値を出力せよ。 - $ 2 $ 行目には，操作の回数を出力せよ。 - $ 2+i $ 行目には，$ i $ 回目の操作で選ぶ要素が，その時点の数列で左から何番目かを出力せよ。 - 最大値を達成する手順が複数存在する場合，そのうちどれを出力しても良い。

5
1 4 3 7 5

11
3
1
4
2

4
100 100 -1 100

200
2
3
1

6
-1 -2 -3 1 2 3

4
3
2
1
2

9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

5000000000
4
2
2
2
2

### 制約 - 入力は全て整数 - $ 2\ \leq\ N\ \leq\ 1000 $ - $ |a_i|\ \leq\ 10^9 $ ### Sample Explanation 1 数列は以下のように変化します。 - $ 1 $ 回目の操作後の数列 : $ 4,\ 3,\ 7,\ 5 $ - $ 2 $ 回目の操作後の数列 : $ 4,\ 3,\ 7 $ - $ 3 $ 回目の操作後の数列 : $ 11(4+7) $ ### Sample Explanation 2 \- $ 1 $ 回目の操作後の数列 : $ 100,\ 200(100+100) $ - $ 2 $ 回目の操作後の数列 : $ 200 $ ### Sample Explanation 3 \- $ 1 $ 回目の操作後の数列 : $ -4,\ 1,\ 2,\ 3 $ - $ 2 $ 回目の操作後の数列 : $ 1,\ 2,\ 3 $ - $ 3 $ 回目の操作後の数列 : $ 4 $