rt，如果有的话，CF，AT，UVA，SPOJ也可以。

---

问题 G: 【一本通提高区间类动态规划】分离与合体

时间限制: $1$ Sec 内存限制: $128$ MB

Judge Mode:Std IO

题目描述

经过在机房里数日的切磋，LYD从杜神牛那里学会了分离与合体，出关前，杜神牛给了他一个测试......

杜神牛造了 $n$ 个区域，它们紧邻着排成了一行，编号 $1\sim n$ 。在这每个区域里都放着一把OI界的金钥匙，每一把都有一定的价值，LYD当然想得到它们了。然而杜神牛规定LYD不可以一下子把它们全部拿走，而是每次只可以拿一个。为了尽快的拿到所有的金钥匙，LYD自然就用上了刚学的分离与合体特技。

一开始LYD可以选择从 $1\sim n-1$ 的任何一个区域(记为 $K$ )进入，进入后LYD会在 $K$ 区域发生分离，从而分离为两个小LYD。分离完成的同时会有一面墙在 $K$ 和 $K+1$ 区域之间升起，从而把 $1\sim k$ 和 $k+1\sim n$ 阻断为两个独立的区间。然后两个小LYD分别进入 $1\sim k$ 和 $k+1\sim n$，并在各自的区间内任选除了区间末尾区域以外(即 $1\sim k$ 或 $k+1\sim n$ )的任何一个区域再次发生分离，就一共有了 $4$ 个小小LYD……重复进行以上所叙述的分离，直到每个小LYD发现自己所在的区间只剩下了一个区域，他们就可以抱起自己梦寐以求的OI金钥匙。

但是LYD不能就这么分成 $n$ 多个个体存在于世界上，这些小LYD还会再合体，合体的两个小LYD所在的区间中间的墙会消失。合体会获得一定的价值，计算方法是：

(合并后所在区间的最左端区域和最右端区域里金钥匙的价值之和) 乘 (之前分离的时候所在区域的金钥匙价值)。

例如：LYD曾经在 $1\sim3$区间中的 $2$ 号区域分离成为 $1\sim2$ 和 $3$ 两个区间，合并时获得的价值就是（ $1$号金钥匙价值+ $3$ 号价值）*( $2$ 号金钥匙价值)。

LYD请你编程求出最终可以获得的总价值最大是多少。并按照分离阶段从前到后，区域从左向右的顺序，输出发生分离的区域编号 (例如：先打印 $1$ 分为 $2$ 的分离区域，然后从左到右打印 $2$ 分为 $4$ 的分离区域，然后是 $4$ 分为 $8$ 的......) 。

注意：若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。

输入

第一行:正整数 $n$ ($2\le n\le300$)

第二行: $n$ 个正整数，表示 $1\sim n$ 区域里每把金钥匙的价值。

保证答案及运算过程中不超出longint范围。

输出

第一行一个数，即获得的最大价值

第二行按照分离阶段从前到后，区域从左向右的顺序，输出发生分离的区域编号，中间用一个空格隔开，若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。

输入输出样例

样例输入

7
1 2 3 4 5 6 7

样例输出

238
1 2 3 4 5 6

提示

对于 $20\%$ 的数据， $n\le10$

对于 $40\%$ 的数据， $n\le50$

对于 $100\%$ 的数据， $n\le300,a_{i}\le300$