题目描述

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$ 个这个数，描述一个合理的出列顺序，输出的是对应同学的“坏值”，详见样例。如果有多个满足条件的出列顺序，请输出出列的人序号字典序最小的。

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

提示

样例解释 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$。