题目内容

某条自动化流水线有 n 个工位，从左到右编号为 $1,2,\dots,n$。现在需要给每个工位分配一个能力等级，等级必须使用 $1,2,\dots,n$，且每个等级恰好使用一次。

一个连续工位段由一对左右端点 $(l,r)$ 确定，其中 $1 \le l \le r \le n$，表示从左端点 $l$ 到右端点 $r$ 的所有工位。该连续工位段的能力和定义为其中所有工位能力等级之和。

定义整条流水线的总增益为：所有不同连续工位段的能力和之和。

对于第 $i$ 个工位，它属于某个连续工位段当且仅当左端点 $l \le i$ 且右端点 $r \ge i$。因此包含该工位的连续工位段数量为 $i \times (n-i+1)$。

你的目标是合理分配等级，使总增益尽可能大。

约束：整数 n 的范围为 1 到 250000（即 $1 \le n \le 250000$）。

输入描述

输入只有一行，包含一个整数 n，表示工位数量，保证 $1 \le n \le 250000$。

输出描述

输出两行。第一行输出一个整数，表示最大总增益对 $10^9+7$ 取模后的结果。第二行输出 n 个整数，表示你的等级序列，相邻整数用一个空格分隔。等级序列必须由 $1,2,\dots,n$ 组成且每个整数恰好出现一次。

如果存在多个最优方案，输出任意一个即可。

样例1

输入

1

输出

1
1

说明

当 n = 1 时，只有一个工位。

位置 1 被包含的连续工位段数量为 $1 \times 1 = 1$，因此权值为 $1$。只能放入等级 1，总增益为 $1 \times 1 = 1$。

对 $10^9+7$ 取模后仍为 1。

样例2

输入

3

输出

21
1 3 2

说明

当 n = 3 时，各位置的权值分别为：

位置 1：$1 \times 3 = 3$； 位置 2：$2 \times 2 = 4$； 位置 3：$3 \times 1 = 3$。

为了让总和最大，应把最大的等级 3 放在权值最大的位置 2，等级 1 和 2 放在两端权值较小的位置。题解构造出的序列为 1 3 2。

总贡献为： $1 \times 3 + 3 \times 4 + 2 \times 3 = 3 + 12 + 6 = 21$。

对 $10^9+7$ 取模后仍为 21。

样例3

输入

4

输出

54
1 3 4 2

说明

当 n = 4 时，各位置的权值分别为：

位置 1：$1 \times 4 = 4$； 位置 2：$2 \times 3 = 6$； 位置 3：$3 \times 2 = 6$； 位置 4：$4 \times 1 = 4$。

中间两个位置权值最大，两端权值较小。将较小的等级 1、2 放在两端，较大的等级 3、4 放在中间，得到序列 1 3 4 2。

总贡献为： $1 \times 4 + 3 \times 6 + 4 \times 6 + 2 \times 4 = 4 + 18 + 24 + 8 = 54$。

对 $10^9+7$ 取模后仍为 54。