Problem Description

Tweetuzki still remembers some things about the instructor of their class during the military training in Grade 7.

There are $n$ students in Tweetuzki’s class, with seat numbers from $1$ to $n$. Once, the instructor ordered the $n$ students to stand in a line from left to right in increasing seat number, where student $1$ is on the far left and student $n$ is on the far right.

Since the students had been standing for a long time and complained a lot, the kind instructor also did not want everyone to be dismissed at the same time and cause chaos, so he came up with a method: the instructor starts from the far left (next to student $1$), walks to the right side of student $n$, then turns back and returns to student $1$. During the trip from student $1$ to student $n$, when the instructor reaches a student, he may choose to dismiss this student from the line, or wait until the return trip to dismiss the student.

However, some students behaved very badly during the training, so the instructor wants them to rest later. For student $i$, define their “badness value” as $w_i$. The instructor wants, within one round trip, to have all students dismissed, and maximize the value of $\sum_{i = 1}^n r_i \times w_i$, where $r_i$ means student $i$ is the $r_i$-th student to be dismissed. The clever instructor immediately found a plan, and Tweetuzki was amazed, so he asked the instructor how to do it. But he is timid and has a large “badness value”, so the instructor might not tell him, and thus he came to you.

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 $w_1, w_2, w_3, …, w_n$ ( $0 \le w_i \le 10^6$ ).

Output Format

The first line contains an integer, the maximum value.
The next line contains $n$ integers describing a valid dismissal order. Output the corresponding students’ “badness values”; see the sample for details. If there are multiple valid dismissal orders, output the one with the lexicographically smallest sequence of dismissed student indices.

5
7 8 1 2 5

87
1 2 5 8 7

5
7 99 1 5 2

530
7 1 2 5 99

8
1 9 2 6 0 8 1 7

206
1 2 0 1 7 8 6 9

Hint

Sample Explanation 1

On the way there, dismiss students $3, 4, 5$. On the way back, dismiss students $2, 1$. The total value is $5 \times 7 + 4 \times 8 + 1 \times 1 + 2 \times 2 + 3 \times 5 = 87$, and it can be proven that no plan can achieve a value greater than $87$.

Constraints

This problem has $20$ test points, and each group of testdata is 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$.

Translated by ChatGPT 5