最近瓦夏决定提高他的手枪射击技巧。今天,他的教练为他提供了以下练习。他把$$$n$$$罐子在桌子上排成一排。罐头从左到右编号为 $$$1$$$ 到 $$$n$$$。瓦西娅必须将每个罐子击倒一次才能完成练习。他可以选择击倒罐子的顺序。
Vasya 知道第 $$$i$$$ 个罐头的耐用性是 $$$a_i$$$。这意味着,如果 Vasya 已经击倒了 $$$x$$$ 罐子,现在正要开始射击第 $$$i$$$ 罐子,那么他将需要 $$$(a_i \cdot x + 1)$$$ 射击才能将其击倒。您可以假设,如果 Vasya 开始射击第 $$$i$$$ 个罐头,他将一直射击它,直到将其击倒。
你的任务是选择这样的射击顺序,以便将给定的每个 $$$n$$$ 罐子击倒一次所需的射击次数尽可能最少。
输入
输入的第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 1\,000)$$$ — 罐数。
输入的第二行包含序列 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 1\,000)$$$,其中 $$$a_i$$$ 是第 $$$i$$$ 罐的耐用性。
输出
在第一行中打印将给定的每个 $$$n$$$ 罐子击倒一次所需的最小射击次数。
在第二行中打印由 $$$n$$$ 不同整数组成的序列,从 $$$1$$$ 到 $$$n$$$ — 罐头索引的顺序,可最大限度地减少所需的射击次数。如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
3 20 10 20
输出 #1
43 1 3 2
输入 #2
4 10 10 10 10
输出 #2
64 2 1 4 3
输入 #3
6 5 4 5 4 4 5
输出 #3
69 6 1 3 5 2 4
输入#4
2 1 4
输出#4
3 2 1
注意
在第一个示例中,Vasya 可以从第一个罐头开始射击。他第一枪就把它击倒了,因为他以前没有击倒过任何其他罐子。之后他必须射击第三罐。为了击倒它,他射击了 $$$20 \cdot 1 + 1 = 21$$$ 次。之后就只剩下第二个了。为了击倒它,瓦夏射击 $$$10 \cdot 2 + 1 = 21$$$ 次。所以总镜头数为$$$1 + 21 + 21 = 43$$$。
在第二个示例中,射击顺序并不重要,因为所有罐子都具有相同的耐用性。