题目描述

给定长度为 $N$ 的整数序列：$a_1, a_2, ..., a_N$。

重复以下操作，直到序列长度变为 $1$：

• 首先，选择序列中的一个元素。
• 如果该元素位于序列的两端，则删除该元素。
• 如果该元素不位于序列的两端，则用其相邻两个元素之和替换该元素。然后，删除这两个元素。

你希望使序列中剩下的最后一个元素的值最大化。

找到最终元素的最大可能值，以及实现该值的方式。

约束条件

• 所有输入值均为整数。
• $2 \leq N \leq 1000$
• $|a_i| \leq 10^9$

输入

从标准输入读入输入数据。输入格式如下：

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

输出

• 在第一行中，打印出序列中最后一个元素的最大可能值。
• 在第二行中，打印出你执行的操作次数。
• 在第 $(2+i)$ 行中，如果在第 $i$ 次操作中所选择的元素是当前序列左侧第 $x$ 个元素，则打印 $x$。
• 如果有多种方式可以达到最大值，则可以任意打印其中一种方式。

示例输入 1

5
1 4 3 7 5

示例输出 1

11
3
1
4
2

序列变化如下：

• 第一次操作后：$4, 3, 7, 5$
• 第二次操作后：$4, 3, 7$
• 第三次操作后：$11(4+7)$

示例输入 2

4
100 100 -1 100

示例输出 2

200
2
3
1

• 第一次操作后：$100, 200(100+100)$
• 第二次操作后：$200$

示例输入 3

6
-1 -2 -3 1 2 3

示例输出 3

4
3
2
1
2

• 第一次操作后：$-4, 1, 2, 3$
• 第二次操作后：$1, 2, 3$
• 第三次操作后：$4$

示例输入 4

9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

示例输出 4

5000000000
4
2
2
2
2