We simply call the \(k\)-th digit from the bottom in binary representation of \(x\) the \(k\)-th digit.
Also, let \(P~\mathrm{OR}~a = (P_1~\mathrm{OR}~a, P_2~\mathrm{OR}~a, \dots, P_N~\mathrm{OR}~a)\).

When \(N\) is a power of \(2\)

Let \(N = 2^n\).
\(P\) should be constructed as follows:

1. Set \(P_i = i-1\).
2. Add \(2^{j+15}\) to \(P_k\). \((0 \leq j \leq n-2\), \(2^j+1 \leq k \leq 2^{j+1})\)

For \(a = x \times 2^{15} ~(x = 0,1,\dots,2^{n-1}-1)\), there is at least one \(a\) for each of \(2^{n-1}+1, 2^{n-1}+2, \dots, N\) such that the LIS length of \(P~\mathrm{OR}~a\) is that value.

Fixing the 1st and 16th digits of \(a\) to \(1\) reduces to the case where \(N=2^{n-1}\).

When \(N\) is not a power of \(2\)

Let \(2^{n-1} < N \leq 2^n\).
From \(P\) for \(N=2^n\), delete odd-indexed elements from the back in order.

\(a\) is the same as when \(N=2^n\).