M - + and Xor Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

正整数 N が与えられます。長さ N の (1,2,\ldots,N) の順列 p について、以下の値を最大化する p を 1 つ求めてください。

  • (p_1 + 1) \oplus (p_2 + 2) \oplus \ldots \oplus (p_N + N)

ただし \oplus はビット単位 \mathrm{XOR} 演算を表します。

ビット単位 \mathrm{XOR} 演算とは

非負整数 A,B のビット単位 \mathrm{XOR} 演算、A\oplus B は、以下のように定義されます。

  • A\oplus B を二進表記した際の 2^k\ (k\geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3\oplus 5 = 6 となります（二進表記すると: 011\oplus 101 = 110)。

制約

  • 1 \leq N \leq 2\times 10^5
  • 入力は全て整数

入力

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

N

出力

問題文中の条件を満たす p を空白区切りで 1 行に出力せよ。

p としてありうるものが複数ある場合、どれを出力してもよい。

入力例 1

3

出力例 1

2 1 3

(2+1) \oplus (1+2) \oplus (3+3) = 6 です。値を 6 より大きくすることができないので、これを出力します。

入力例 2

1

出力例 2

1

入力例 3

5

出力例 3

2 3 4 5 1