Outline: considering the operations in reverse order works.

First, consider the following [Problem ☆].

For \(i=N,N-1,\ldots,1\) in order, perform the following operation against \(A'=(1,2,\ldots,N)\):

• Operation: remove the \(P_i\)-th element from \(A'\) to obtain a new array shorter than one element.

Find \(B_i\), defined as the number removed in each step.

Define the following array.

\(T[i] = 1\) if \(i\) is contained in \(A'\), and \(0\) otherwise

Since \(A'\) is always monotonically increasing throughout the procedure, so the \(p\)-th element of \(A'\) is the smallest \(x\) with \(\sum_{i=1}^ {x}T[i]=p\). Thus, it can be found fast if we can perform binary search over the cumulative sums of \(T\).
Removing the value \(i\) from \(A'\) corresponds to setting \(T[i]\) to \(0\), so [Problem ☆] can be solved fast with a data structure that supports element-wise update and segment-wise sum retrieval - which is realized with a Fenwick Tree or a segment tree. Thus, the problem can be solved in a total of \(O(N\log N)\) time.

Let \(A=(A_1,\ldots,A_N)\) be the answer to the original problem, that is, the sequence after the procedure.
Considering the correspondence between [Problem ☆], \(B_i\) intuitively represents the final position of the number inserted for the \(i\)-th time in the original problem. This implies \(A_{B_i}=i\), so once [Problem ☆] is solved, the answer can be found in \(O(N)\) time.