Problem Description

Tweetuzki still remembers some stories about their class instructor during their first year of military training.

Tweetuzki's class has $n$ students, numbered from $1$ to $n$. Once, the instructor ordered the $n$ students to stand in a line from left to right in order of their seat numbers, with student $1$ on the far left and student $n$ on the far right.

Due to the long standing, there was a lot of grumbling. The kind-hearted instructor did not want everyone to disperse at once, causing chaos, so he came up with a plan: the instructor would start from the leftmost position, which is next to student $1$, walk to the right side of student $n$, and then return to the side of student $1$. During the instructor's walk from student $1$ to student $n$, whenever he reached a student, he could choose to let that student step out of line, or wait until the return trip to do so.

However, some students behaved very poorly during the training, so the instructor wanted them to step out later. For student $i$, define their "badness value" as $w_i$. The instructor hopes to maximize the value of $\sum_{i = 1}^n r_i \times w_i$ in one round trip, where $r_i$ represents the order in which student $i$ steps out. The clever instructor immediately came up with a solution, which amazed Tweetuzki. He wanted to ask the instructor how he did it, but he was too timid and had a high "badness value," so the instructor might not tell him. Therefore, he turned to you for help.

Input Format

The first line contains an integer $n$ ($5 \le n \le 10^6$).
The second line contains $n$ integers describing the badness values of the $n$ students, $w_1, w_2, w_3, \ldots, w_n$ ($0 \le w_i \le 10^6$).

Output Format

The first line contains an integer representing the maximum value.
The next line contains $n$ integers describing a valid sequence of stepping out, outputting the corresponding "badness values" of the students. If there are multiple valid sequences, output the one with the lexicographically smallest sequence of student numbers.

Sample Input and Output

Sample Input #1

5
7 8 1 2 5

Sample Output #1

87
1 2 5 8 7

Sample Input #2

5
7 99 1 5 2

Sample Output #2

530
7 1 2 5 99

Sample Input #3

8
1 9 2 6 0 8 1 7

Sample Output #3

206
1 2 0 1 7 8 6 9

Notes

Sample Explanation 1

On the way there, let students $3, 4, 5$ step out, and on the way back, let students $2, 1$ step out. The total value is $5 \times 7 + 4 \times 8 + 1 \times 1 + 2 \times 2 + 3 \times 5 = 87$. It can be proven that there is no plan that yields a value greater than $87$.

Data Range

There are a total of $20$ test cases, each worth $5$ points.

For $10\%$ of the data, $n \le 8$.
For $30\%$ of the data, $n \le 20$.
For $60\%$ of the data, $n \le 1000$.
For $100\%$ of the data, $5 \le n \le 10^6$, $0 \le w_i \le 10^6$.

见题面 Input 部分

见题面 Output 部分