AT_nupc2024_q.Stablest Permutation

对于 $ (1,2,\dots,N) $ 的一个排列 $ P=(P_1,P_2,\dots,P_N) $，定义该排列的不安定性如下：

$$\max_{1 \leq i < j \leq N} \left|\operatorname{inv}(P^{i,j}) - \operatorname{inv}(P)\right|$$

其中，$P^{i,j}$ 表示将排列 $P$ 的第 $i$ 项与第 $j$ 项交换后的新排列，$\operatorname{inv}(X)$ 表示排列 $X$ 的逆序对数。

给定一个整数 $N$，请构造一个使上述不安定性最小的 $ (1,2,\dots,N) $ 的排列，并输出其中之一。

逆序对数定义如下：对于一个序列 $ (A_1,A_2,\dots,A_N) $，逆序对数是满足 $1 \leq i < j \leq N$ 且 $A_i > A_j$ 的整数对 $(i, j)$ 的数目。

输入包含一行：

$ N $

输出一个长度为 $N$ 的排列，排列由 $1$ 到 $N$ 组成，并且不安定性最小。各数用空格分隔。若有多个解，输出其中任意一个即可。

样例解释 1

不安定性为 $3$，无法进一步减小。

数据范围

• $2 \leq N \leq 2 \times 10^5$
• 输入均为整数。

由 ChatGPT 5 翻译