大样例下载

题目描述

有 $n$ 根小木棍连接在一起，左数第 $i$ 根小木棍编号为 $i$，其长度为 $L_i$，共有 $n-1$ 个连接处。

现在你要砍断所有的连接处。

每次，你只能砍断一个连接处。每砍一次，你会得到一定的劳动报酬。

假设当前你要砍的一段大木棍，其最左端小木棍的编号为 $x$，最右端小木棍的编号为 $y$，而你要砍断的，是编号 $z$ 和 $z+1$ 的小木棍之间的连接处（显然，$x ≤ z < y$），则你这一次砍木棍得到的报酬为 $(L_x + L_y) * L_z$。

你自然希望得到总报酬最多。问：如何安排砍小木棍连接处的顺序，可以得到最多的总报酬？你需要输出可以得到的最多的总报酬，以及砍木棍的方案。

方案输出，你只需要按砍的顺序输出每次砍断的是哪一根木棍后面的连接处。如果有多种方案，你需要输出字典序最小的那种方案。

输入格式

第一行：一个整数 $n$

第二行：$n$ 个整数 $L_i$

输出格式

第一行：一个整数，表示最多总报酬。

第二行：$n-1$ 个整数，表示字典序最小的砍木棍方案，其中第 $i$ 个整数 $z_i$ 表示第 $i$ 次砍断的是编号为 $z_i$ 与 $z_i+1$ 的小木棍之间的连接处。

样例输入

4
1 2 2 1

样例输出

16
1 3 2

数据范围

20% 的数据：$n ≤ 10$；

40% 的数据：$n ≤ 50$；

100% 的数据：$n, L_i ≤ 300$，数据保证答案不超过 $（2^{31}-1）$