该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

打倒了怪物，你顺利进入入口。
你眼前出现了\(n\)个区域，上面写着：

将所有钥匙合并成一个价值最大的钥匙，才能打开这扇门。

旁边放着一本书：《分身与合体》

问题描述

一共有\(n\)个区域，他们紧邻着排成一行，编号1~\(n\)，在每个区域里都放着一把钥匙。然而你不能一下子把他们全部拿走，而是每次只可以拿一把。为了尽快得到所有钥匙，你自然就用上了刚学的分身与合体特技。
一开始你可以选择1~\(n\) - 1中的任何一个区域进入，我们不妨把这个区域记为\(k\)。进入后你会在\(k\)区域发生分离，从而分出成两个分身。分离完成的同时会有一面墙在\(k\)区域和\(k\)+1区域间升起，从而把1~\(k\)和\(k\)+1~\(n\)阻断成两个独立的区间，并在各自区间内任选除区间末尾之外（即从1~\(k\)−1和\(k\)+1~\(n\)−1中选取）的任意一个区域再次发生分离，这样就有了四个分身……重复以上所叙述的分离，直到每个分身发现自己所在的区间只剩下了一个区域，那么他们就可以抱起自己梦寐以求的钥匙。
但是你不能就分成这么多个个体存在于世界上，这些分身还会再合体，合体的分身所在区间中间的墙会消失。合体会获得((合并后所在区间左右端区域里金钥匙价值之和)×(之前分离的时候所在区域的金钥匙价值))。
例如，你曾在1~3区间中的2号区域分离成为1~2和3~3两个区间，合并时获得的价值就是 ((1号钥匙价值+3号金钥匙价值)×(2号金钥匙价值))。
你想知道最终可以获得的最大总价值，并按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。
注意：若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。

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

输入格式

第1行一个正整数\(n\)，表示共有\(n\)个区域。
第2行，\(n\)个用空格分开的正整数\(ai\)，表示1~\(n\)区域里每把钥匙的价值。

输出格式

第1行一个数，表示获得的最大价值
第2行按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。

样例数据

样例输入1

7
1 2 3 4 5 6 7

样例输出1

238
1 2 3 4 5 6

提示

• 样例解释

  【输入输出样例1解释】
  总和为：
  
(6 + 7) * 6 + (5 + 7) * 5 + (4 + 7) * 4 + (3 + 7) * 3 + (2 + 7) * 2 + (1 + 7) * 1


• 数据范围

  对于%10的数据，\(n\)<=10；
  对于%30的数据，\(n\)<=50；
  对于%50的数据，\(n\)<=100；
  对于%80的数据，\(n\)<=300；
  对于%100的数据，0<\(n\)<=500，0<\(ai\)<=300；

限制

时间限制：1s。
空间限制：256MB。