Tweetuzki 爱军训

题目描述

Tweetuzki 仍然记得,初一军训的时候,有关他们班的教官的一些事儿。 Tweetuzki 所在的班级有 $n$ 名学生,座号从 $1$ 到 $n$。有一次,教官命令班上的 $n$ 名学生按照座号顺序从左到右排成一排站好军姿,其中 $1$ 号学生在最左边,$n$ 号学生在最右边。 由于同学们站了很久,怨声载道,仁慈的教官又不希望大家一起解散导致混乱的局面,于是想了一个办法:教官从最左边——也就是 $1$ 号学生身旁出发,走到 $n$ 号学生右边后,再折返回到 $1$ 号同学旁边。在教官在从 $1$ 号同学走到 $n$ 号同学这段路上,当走到某位同学身边时,他可以选择让这位同学出列,也可以等到折返的时候再使这名同学出列。 但是有一些同学在军训过程中表现极坏,因此教官希望他们晚一些出列休息。对于 $i$ 号同学,定义他的“坏值”为 $w_i$。教官希望在一次往返过程中,使得所有学生出列,且最大化 $\sum_{i = 1}^n r_i \times w_i$ 的值,其中 $r_i$ 表示 $i$ 号同学是第 $r_i$ 位出列的学生。机智的教官一下子就想出了这个方案,Tweetuzki 大为惊讶,于是他去请教教官如何做到。可是他的胆子很小而且“坏值”很大,教官可能不会告诉他,所以他就找到了你。

输入输出格式

输入格式


第一行一个整数 $n$ ( $5 \le n \le 10^6$ )。 第二行包含 $n$ 个整数,描述这 $n$ 个同学的坏值 $w_1, w_2, w_3, …, w_n$ $(0 \le w_i \le 10^6)$。

输出格式


第一行一个整数,表示最大值。 接下来一行包含 $n$ 个这个数,描述一个合理的出列顺序,输出的是对应同学的“坏值”,详见样例。如果有多个满足条件的出列顺序,请输出出列的人序号字典序最小的。

输入输出样例

输入样例 #1

5
7 8 1 2 5

输出样例 #1

87
1 2 5 8 7

输入样例 #2

5
7 99 1 5 2

输出样例 #2

530
7 1 2 5 99

输入样例 #3

8
1 9 2 6 0 8 1 7

输出样例 #3

206
1 2 0 1 7 8 6 9

说明

### 样例解释 1 在去的路上让 $3, 4, 5$ 号同学出列,回来时让 $2, 1$ 号同学出列。总的值为 $5 \times 7 + 4 \times 8 + 1 \times 1 + 2 \times 2 + 3 \times 5 = 87$,可以证明没有使得答案大于 $87$ 的方案。 ### 数据范围 本题共设 $20$ 组测试点,每组测试数据 $5$ 分。 对于 $10\%$ 的数据,$n \le 8$。 对于 $30\%$ 的数据,$n \le 20$。 对于 $60\%$ 的数据,$n \le 1000$。 对于 $100\%$ 的数据,$5 \le n \le 10^6$,$0 \le w_i \le 10^6$。