\(x\) の \(2\) 進数における下から \(k\) 桁目を単に \(k\) 桁目と呼びます。
また、\(P~\mathrm{OR}~a = (P_1~\mathrm{OR}~a, P_2~\mathrm{OR}~a, \dots, P_N~\mathrm{OR}~a)\) とします。

\(N\) が \(2\) べきのとき

\(N = 2^n\) とします。
\(P\) は以下の手順で構築すればよいです。

1. \(P_i = i-1\) とする。
2. \(P_k\) に \(2^{j+15}\) を加算する。\((0 \leq j \leq n-2\)、\(2^j+1 \leq k \leq 2^{j+1})\)

\(a = x \times 2^{15} ~(x = 0,1,\dots,2^{n-1}-1)\) とすると、\(P~\mathrm{OR}~a\) の LIS の長さが \(2^{n-1}+1, 2^{n-1}+2, \dots, N\) になるようなものがそれぞれ \(1\) つ以上あります。

\(a\) の \(1,16\) 桁目を \(1\) で固定すると \(N=2^{n-1}\) の場合に帰着できます。

\(N\) が \(2\) べきでないとき

\(2^{n-1} < N \leq 2^n\) とします。
\(N=2^n\) における \(P\) から、奇数番目の要素を後ろから順に削除すればよいです。

\(a\) は \(N=2^n\) のときと同様です。