该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于一个整数 $n \in \Z^+$，定义：

• $[n]=\{1,2,\ldots,n\}$。

• $\mathcal{S_n}=\left\{\sigma \in [n]^n \mid (\nexists i,j \mid 1 \le i < j \le n \land \sigma_i = \sigma_j) \right\}$。

• $\mathcal{F_n}=\left\{\mathcal{P}\subseteq [n] \mid \forall i \in [n-1], \neg(i \in \mathcal{P} \land i + 1\in \mathcal{P})\right\}$ 。

对于一个长度为 $n$ 的数组 $a$，定义：

• $f(a)=\max_{\mathcal{P}\in \mathcal{F}_n}\left(\sum_{i \in \mathcal{P}}a_i\right)$。

定义 $\psi(n)=\min_{\pi \in \mathcal{S}_n}f(\pi)$。给定一个整数 $n$，你需要计算 $\psi(n)$，并找到任意 $\pi \in \mathcal{S}_n$ 使得 $f(\pi)=\psi(n)$。

输入格式

输入包含一个正整数 $n$。

输出格式

输出共两行。 第一行输出一个整数，表示 $\psi(n)$ 的值。 第二行输出 $n$ 个用空格隔开的整数，表示一个满足 $f(\pi) = \psi(n)$ 的排列 $\pi$。

如果存在多个满足条件的排列，输出任意一个即可。

输入输出样例

5

8
1 2 3 5 4

提示

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$。