6954: 「一本通 5.1 练习 2」分离与合体
[Creator : ]
Description
经过在机房里数日的切磋，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$ 阻断成两个独立的区间，并在各自区间内任选除区间末尾之外（即从 $1 \sim k-1$ 和 $k+1 \sim n-1$ 中选取）的任意一个区域再次发生分离，这样就有了四个小小 LYD……重复以上所叙述的分离，直到每个小 LYD 发现自己所在的区间只剩下了一个区域，那么他们就可以抱起自己梦寐以求的 OI 金钥匙。
但是 LYD 不能就分成这么多个个体存在于世界上，这些小 LYD 还会再合体，合体的小 LYD 所在区间中间的墙会消失。合体会获得 (合并后所在区间左右端区域里金钥匙价值之和) $\times$ (之前分离的时候所在区域的金钥匙价值)。
例如，LYD 曾在 $1 \sim 3$ 区间中的 $2$ 号区域分离成为 $1 \sim 2$ 和 $3 \sim 3$ 两个区间，合并时获得的价值就是 ($1$ 号金钥匙价值 + $3$ 号金钥匙价值) $\times$ ($2$ 号金钥匙价值)。
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$ 阻断成两个独立的区间，并在各自区间内任选除区间末尾之外（即从 $1 \sim k-1$ 和 $k+1 \sim n-1$ 中选取）的任意一个区域再次发生分离，这样就有了四个小小 LYD……重复以上所叙述的分离，直到每个小 LYD 发现自己所在的区间只剩下了一个区域，那么他们就可以抱起自己梦寐以求的 OI 金钥匙。
但是 LYD 不能就分成这么多个个体存在于世界上，这些小 LYD 还会再合体，合体的小 LYD 所在区间中间的墙会消失。合体会获得 (合并后所在区间左右端区域里金钥匙价值之和) $\times$ (之前分离的时候所在区域的金钥匙价值)。
例如，LYD 曾在 $1 \sim 3$ 区间中的 $2$ 号区域分离成为 $1 \sim 2$ 和 $3 \sim 3$ 两个区间，合并时获得的价值就是 ($1$ 号金钥匙价值 + $3$ 号金钥匙价值) $\times$ ($2$ 号金钥匙价值)。
LYD 请你编程求出最终可以获得的最大总价值，并按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。
例如先打印一分为二的区域，然后从左到右打印二分为四的分离区域，然后是四分为八的……
Input
第一行一个正整数 $n$
第二行 $n$ 个用空格分开的正整数 $a_i$，表示 $1 \sim n$ 区域里每把金钥匙的价值。
第二行 $n$ 个用空格分开的正整数 $a_i$，表示 $1 \sim n$ 区域里每把金钥匙的价值。
Output
第一行一个数，表示获得的最大价值
第二行按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。
第二行按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。
Constraints
对于 $20\%$ 的数据，$n\le 10$；
对于 $40\%$ 的数据，$n\le 50$；
对于 $100\%$ 的数据，$n,a_i\le 300$，保证运算过程和结果不超过 $32$ 位正整数范围。
对于 $40\%$ 的数据，$n\le 50$；
对于 $100\%$ 的数据，$n,a_i\le 300$，保证运算过程和结果不超过 $32$ 位正整数范围。
Sample 1 Input
7
1 2 3 4 5 6 7
Sample 1 Output
238
1 2 3 4 5 6