题目描述

あなたは，長さ $N$ の数列 $a_1,\ a_2,\ ...,\ a_N$ を持っています。

あなたは，この数列の長さが $1$ になるまで，繰り返し以下の操作を行います。

• まず，数列の要素を $1$ つ選ぶ。
• もしその要素が数列の端だった場合，その要素を削除する。
• もしその要素が数列の端でない場合，その要素を，選んだ要素の両隣の要素の和に書き換える。そしてその後，両隣の要素を削除する。

あなたは，最終的な数列の要素の値を最大化したいです。

最終的な数列の要素の値の最大値と，それを達成する手順を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $a_2$ $...$ $a_N$

输出格式

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

题目大意

给你一个长度为 n (2≤n≤1000) 的序列 a |ai|<=1e9 。可以选择以下操作：

1.选择一个端点的数，删除

2.选择一个非端点的数，将其变为相邻左右两数之和，删去左右两边的数。

若干次操作后序列只剩下一个数，要求结果尽可能大。求每次选数方案。

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$