题目描述

杜神牛造了 $n$ 个区域，它们紧邻着排成一行，编号为 $1$ 到 $n$。每个区域里都有一把金钥匙，第 $i$ 把金钥匙的价值为 $a_i$。

一开始，LYD 可以选择 $1$ 到 $n-1$ 中的任意一个区域 $k$ 发生分离，使区间 $[1,n]$ 被分成 $[1,k]$ 和 $[k+1,n]$ 两个独立区间。之后，每个长度大于 $1$ 的区间都可以继续选择一个分离位置，直到每个区间只剩下一个区域。

分离结束后，小 LYD 会再合体。若某次分离发生在区域 $k$，合并后的区间左右端区域金钥匙价值分别为 $a_l$ 和 $a_r$，则这次合体获得的价值为 $(a_l+a_r) \times a_k$。

请计算最终可以获得的最大总价值，并按照分离阶段从前到后、区域从左到右的顺序，输出发生分离的区域编号。若有多种最优方案，选择输出字典序最小的方案。

输入格式

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

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每把金钥匙的价值。

输出格式

第一行输出一个整数，表示可以获得的最大总价值。

第二行输出若干个整数，表示发生分离的区域编号，相邻整数之间用一个空格分隔。

7
1 2 3 4 5 6 7

238
1 2 3 4 5 6

数据范围与提示

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

来源

一本通 5.1 练习 2