题目描述

铁轨上从左到右停着 $n$ 节车厢，编号依次为 $1,2,\ldots,n$。每节车厢都装有货物，并具有一定质量。

车厢最开始彼此没有连接。

若若干连续车厢已经连接在一起，我们称它们构成一个列车组。

Józef 负责连接车厢。若要连接两个相邻的列车组，并且它们的总质量分别为 $a$ 吨和 $b$ 吨，那么这次连接操作需要支付

$a+b$

兹罗提。

特别地，最开始连接两节相邻单独车厢时，费用同样等于这两节车厢质量之和。

最终需要把所有 $n$ 节车厢连接成一个整体。

请你确定连接操作的顺序，使总费用最小，并输出这个最小费用以及一种达到最优值的连接顺序。

输入格式

第一行包含一个整数 $n$：

$1\le n\le3000$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$：

$0\le a_i\le10^4$，

其中 $a_i$ 表示第 $i$ 节车厢最开始的质量。

输出格式

第一行输出一个整数，表示把全部车厢连接起来的最小总费用。

第二行输出 $n-1$ 个整数，描述一种达到最优费用的连接顺序。

输出整数 $i$ 表示：

将当前“第一节车厢编号为 $i$”的列车组，与它右边紧邻的列车组连接起来。

如果存在多种最优方案，可以输出任意一种。

当 $n=1$ 时，不需要进行连接操作，第二行为空行。

样例

4
3 2 2 3

20
3 1 1

样例说明

一种最优过程如下：

1. 连接车厢 $1$ 和 $2$，费用为 $3+2=5$；
2. 连接车厢 $3$ 和 $4$，费用为 $2+3=5$；
3. 将列车组 $(1,2)$ 与 $(3,4)$ 连接，费用为 $5+5=10$。

总费用为 $20$。

输出的操作编号只要求按照题目定义描述一组当前相邻列车组的合并顺序，因此不唯一。

子任务