题目描述

你有一个长度为 $N$ 的数列 $a_1,\ a_2,\ ...,\ a_N$。

你需要不断重复以下操作，直到数列的长度变为 $1$：

• 首先，从数列中选择一个元素。
• 如果该元素在数列的两端，则将其删除。
• 如果该元素不在数列的两端，则将其替换为其左右相邻元素之和，然后删除这两个相邻元素。

你希望最终数列中唯一剩下的元素的值最大。请输出最终数列元素的最大值，以及实现该最大值的操作步骤。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

• 第 $1$ 行输出最终数列元素的最大值。
• 第 $2$ 行输出操作的总次数。
• 接下来的每一行，第 $i$ 行（$i$ 从 $1$ 到操作次数），输出第 $i$ 次操作时所选择的元素在当前数列中的位置（从左到右编号）。

如果存在多种实现最大值的操作方案，输出其中任意一种即可。

样例 1

输入

5
1 4 3 7 5

输出

11
3
1
4
2

样例 2

输入

4
100 100 -1 100

输出

200
2
3
1

样例 3

输入

6
-1 -2 -3 1 2 3

输出

4
3
2
1
2

样例 4

输入

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$

样例解释 1

数列变化如下：

• 第 $1$ 次操作后数列：$4,\ 3,\ 7,\ 5$
• 第 $2$ 次操作后数列：$4,\ 3,\ 7$
• 第 $3$ 次操作后数列：$11\ (4+7)$

样例解释 2

• 第 $1$ 次操作后数列：$100,\ 200\ (100+100)$
• 第 $2$ 次操作后数列：$200$

样例解释 3

• 第 $1$ 次操作后数列：$-4,\ 1,\ 2,\ 3$
• 第 $2$ 次操作后数列：$1,\ 2,\ 3$
• 第 $3$ 次操作后数列：$4$

由 ChatGPT 4.1 翻译