概略：操作を逆順に考えるとうまくいきます。

まず次のような[問題☆]を考えます。

\(A'=(1,2,\ldots,N)\) に対し、\(i=N,N-1,\ldots,1\) の順に以下の操作を行う

• 操作：\(A'\) の \(P_i\) 番目の要素を削除し、残りの要素は順序を保って詰める。

各操作で削除される数を \(B_i\) とする。これを求めよ。

次のような配列を用意します。

\(T[i]= i が A' に含まれていれば1、いなければ0\)

操作の過程で \(A'\) は単調増加の状態を保つので、\(A'\) の \(p\) 番目の要素は、\(\sum_{i=1}^ {x}T[i]=p\) を満たす最小の \(x\) です。よって、\(T\) の累積和を二分探索することができれば高速に求めることができます。
\(A'\) から値 \(i\) を削除することは、\(T[i]\) を \(0\) に変更することに対応することから、[問題☆]は \(T\) に対する1点更新・区間和取得が高速にできれば高速に解くことができます。fenwick tree や segment tree などを用いることで全体で \(O(N\log N)\) 時間で解くことができます。

元の問題の答え、すなわち操作後の数列を \(A=(A_1,\ldots,A_N)\) とします。
[問題☆]との対応を考えると、\(B_i\) は直感的には「元の問題において \(i\) 回目の操作で挿入される数は、全ての操作を終えたときどの位置にあるか」を表しているといえます。すなわち、 \(A_{B_i}=i\) となり、[問題☆]が解ければ \(O(N)\) 時間で答えを求めることができます。