Let \(L\) be the LIS length of \(P\). Also, let \(ans=(ans_1,\cdots,ans_N)\) be the answer we seek.

For each element \(P_i\), let \(v_i\) be the maximum length of an increasing subsequence starting from it.

Assume that \(v_i\) is updated with each swap operation. First, for each \(P_i\), the corresponding \(v_i\) never decreases. (Note that we are considering the correspondence from \(P_i\) to \(v_i\), not from \(i\) to \(v_i\).)

Let the indices \(i\) where \(v_i=L\) be \(i_1<i_2<\cdots<i_k\). For each \(i_j\), no value smaller than it can come to its left. Otherwise, the LIS length of \(P\) would exceed \(L\).

Then, we can see that the first \(k\) elements of \(ans\) will be \(P_{i_1},\cdots,P_{i_k}\). Note that there always exists a sequence of operations to reach such a permutation. We simply need to bring each element to the front one by one.

If \(P_{i_k}>1\), we can make \(ans_{k+1}=1\). This can be achieved by bringing \(1\) to the front.

Now, we have processed the elements where \(v_i=L\) and the element where \(P_i\) is minimum (\(1\) in this case), but we can process \(v_i=L-1,L-2,\cdots\) in exactly the same manner. The values of \(v_i\) can all be computed at the beginning and do not need to be updated thereafter.

Therefore, by implementing the above operations directly, we obtain a solution with overall time complexity \(O(N \log N)\).

Writer’s solution (C++)