You are playing the deadly game Game of Destruction. You will be given a list of integers. In each step of this game you have to choose a random integer from the list. You will destroy the integer from the list. For destroying this you will get integer × l (l is the length of list) points. After destroying this integer, this list will be divided into 2 different list. You have to consider every list differently. You have to choose the left list first and keep playing. If you are done with the left list then choose the right one. You will keep destroying integers until there are no list which contain any integer and then the game ends. Total points will be the sum of points in each step.
Now, you are playing this game. As you are a programmer you have to play optimally so that you can get maximum total points. Your task is to find out what is maximum total points you can get, if you play optimally and also find out the sequence of destroying numbers.
Suppose, the list is [1, 4, 7, 2]. Choose 7 first. You will get 7 × 4 = 28 points. Then there will be 2 different list.
[1, 4] and [2]. Now you have to choose the left sided list first. All the steps are given below:
[1, 4, 7, 2] choose 7 and get 7 × 4 = 28 points.
[1, 4] [2] choose 4 and get 4 × 2 = 8 points.
[1] [2] choose 1 and get 1 × 1 = 1 points.
[2] choose 2 and get 2 × 1 = 2 points.
So, total points 28 + 8 + 1 + 2 = 39 points and the sequence will be [3, 2, 1, 4]. This is the optimal option we can choose.
Input
First line contains an integer N (1 ≤ N ≤ 500), --the length of given list.
Next line contains N integers ai (0 ≤ ai ≤ 106).
Output
Print the maximum points in first line.
Print the sequence of destroying integers in next line. If there are different options of choosing integers, choose the one with small index. For the sequence print their indexes (1 based) on given list.
Sample
| Input | Output |
|---|---|
4 1 3 4 1 | 24 3 2 1 4 |
