好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

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

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

一开始 LYD 可以选择 $1..n-1$ 中的任何一个区域进入，我们不妨把这个区域记为 $k$。进入后 LYD 会在 $k$ 区域发生分离，从而分离成两个小 LYD。分离完成的同时会有一面墙在 $k$ 区域和 $k+1$ 区域间升起，从而把 $1..k$ 和 $k+1..n$ 阻断成两个独立的区间，并在各自区间内任选除区间末尾之外（即从 $1..k-1$ 和 $k+1..n-1$ 中选取）的任意一个区域再次发生分离，这样就有了四个小小 LYD……重复以上所叙述的分离，直到每个小 LYD 发现自己所在的区间只剩下了一个区域，那么他们就可以抱起自己梦寐以求的 OI 金钥匙。

但是 LYD 不能就分成这么多个个体存在于世界上，这些小 LYD 还会再合体，合体的小 LYD 所在区间中间的墙会消失。合体会获得
[ (\text{合并后所在区间左右端区域里金钥匙价值之和}) \times (\text{之前分离的时候所在区域的金钥匙价值}) ]

例如，LYD 曾在 $1..3$ 区间中的 $2$ 号区域分离成为 $1..2$ 和 $3..3$ 两个区间，合并时获得的价值就是
[ (1 \text{号金钥匙价值} + 3 \text{号金钥匙价值}) \times (2 \text{号金钥匙价值}) ]

LYD 请你编程求出最终可以获得的最大总价值，并按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。

例如先打印一分为二的区域，然后从左到右打印二分为四的分离区域，然后是四分为八的……

---

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个用空格分开的正整数 $a_i$，表示 $1..n$ 区域里每把金钥匙的价值。

---

输出格式

第一行一个整数，表示获得的最大价值。

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

---

样例

样例输入

7
1 2 3 4 5 6 7

样例输出

238
1 2 3 4 5 6

样例解释

$n=7$，金钥匙价值 $[1,2,3,4,5,6,7]$。

这是一个类似 最优二叉搜索树 或 区间 DP 的问题，相当于每次选择一个分界点 $k$ 将区间 $[l,r]$ 分成 $[l,k]$ 和 $[k+1,r]$，得分 $(a_l + a_r) \times a_k$。

最优划分方案是：

1. 第一层（整个区间 $[1,7]$）选择 $k=1$ 分离；
2. 第二层（区间 $[1,1]$ 不再分，区间 $[2,7]$）选择 $k=2$ 分离；
3. 第三层（$[2,2]$ 不再分，区间 $[3,7]$）选择 $k=3$ 分离；
4. 依次类推，每次分离选择区间左端点 $k=l$。

分离区域顺序（按阶段、从左到右）：

• 阶段1：整个区间 $[1,7]$ 分离在 $1$；
• 阶段2：区间 $[2,7]$ 分离在 $2$；
• 阶段3：区间 $[3,7]$ 分离在 $3$；
• 阶段4：区间 $[4,7]$ 分离在 $4$；
• 阶段5：区间 $[5,7]$ 分离在 $5$；
• 阶段6：区间 $[6,7]$ 分离在 $6$。

因此输出分离区域编号序列：$1\ 2\ 3\ 4\ 5\ 6$。

最大总价值 $238$ 由这些分离产生的合体得分累加得到。

---

数据范围

• 对于 $20\%$ 的数据，$n \le 10$；
• 对于 $40\%$ 的数据，$n \le 50$；
• 对于 $100\%$ 的数据，$n, a_i \le 300$，保证运算过程和结果不超过 $32$ 位正整数范围。

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 区间 DP + 方案输出 问题。

设 $dp[l][r]$ 表示区间 $[l, r]$ 能获得的最大价值。
状态转移：

$$dp[l][r] = \max_{l \le k \le r-1} \{ dp[l][k] + dp[k+1][r] + (a_l + a_r) \times a_k \}$$

其中 $k$ 是分离点（区间 $[l,r]$ 在 $k$ 处分离为 $[l,k]$ 和 $[k+1,r]$）。

初始化：$dp[i][i] = 0$。

方案输出：在 DP 转移时记录 $mid[l][r] = k$，表示最优的分离点。
然后按分离阶段 BFS 或 DFS 输出分离点。