There are n people standing in a queue. The age of the ith person is ai. The more the age gap between two persons, the more uncomfortable they feel with each other. We define the level of discomfort between person i and j as | ai - aj |. Also, the total discomfort of the queue is the sum of the level of discomfort between all adjacent pairs.
Now, you have been given the responsibility of rearranging the queue. A normal person would seek to minimize the total discomfort to help the poor souls. But you are not a normal person, are you? (Besides, that would make the problem very easy). You have an evil heart, so you want to rearrange the queue so that the total discomfort of the queue is as large as possible. Now you need to find the maximum total discomfort you can achieve by rearranging the queue and the rearrangement that achieves it.
Formally, you are given n integers, a1, a2, . . . an. You have to find an permutation p of integers 1, 2, . . . n such that the quantity $\sum_{i=1}^{n-1} |a_{p_i} - a_{p_{i+1}}|$ is maximized.
The first line of the input contains a single integer n (2 ≤ n ≤ 2 × 105).
The second line contains n space separated integers a1, a2, . . . an (1 ≤ ai ≤ 109).
On the first line, print a single integer, the maximum total discomfort you can achieve.
On the second line, print n integers, the permutation that achieves the maximum total discomfort.
Note that, you need to print a permutation of the indices, not the actual values. Each index from 1 to n should appear exactly once in the permutation. If there are multiple possible permutations that achieve the maximum, you may print any of them.
| Input | Output |
|---|---|
3 2 5 9 | 11 1 3 2 |
The total discomfort for the permutation 1, 3, 2 is |a1-a3| + |a3-a2| = 7 + 4 = 11. No other permutation achieves a larger total discomfort. 2, 3, 1 is also an acceptable answer as it achieves the same total discomfort. | |
| Input | Output |
|---|---|
4 1 2 2 1 | 3 4 3 1 2 |
| Input | Output |
|---|---|
2 10 20 | 10 1 2 |