Q - Stablest Permutation 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) の不安定さを以下で定めます。

$$ \max_{1 \leq i < j \leq N} \left|(P_iとP_jを入れ替えた順列の転倒数)-(Pの転倒数)\right| $$

入力で N が与えられます。 (1,2,\dots,N) の順列のうち、不安定さが最小のものを一つ構築してください。

転倒数とは? 数列 (A_1,A_2,\dots,A_N) の転倒数とは、 1 \leq i < j \leq N かつ A_i > A_j を満たす整数組 (i,j) の個数を指します。

制約

  • 2\leq N\leq 2\times10^5
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N

出力

(1,2,\dots,N) の順列のうち不安定さが最小のものを一つ、空白区切りで出力してください。解が複数存在する場合、どれを出力しても正解とみなされます。

入力例 1

7

出力例 1

6 2 1 5 7 3 4

不安定さは 3 で、これより小さくすることはできません。