Original proposer: vwxyz

Values that are never removed all remain at the beginning of \(P\), preserving their order.
One can prepare a length-\(N\) array initially filled with \(0\), and set the \(a_i\)-th element to \(1\) for each \(q=1,2,\dots,Q\), in order to determine whether \(1,2,\dots,N\) are touched in a total of \(O(N)\) time.
By arranging the elements of \(P\) that are not touched, this part can be processed in \(O(N)\) time.

Next, consider the order of elements that are removed at least once.
An element once removed and appended to \(P\) may be touched again by another operation, so it cannot be handled naively.
However, if the element is touched for the last time, it is never removed from \(P\) afterward.
In such cases, it is often effective to employ the trick of inspecting the operations in reverse order; this problem can be solved this way, too.
Prepare an array \(M'\), initially empty.
For \(q=Q,Q-1,\dots,1\) in order, check if \(a_q\) is an operation occurring for the first time in reverse order (or the last operation \(a_q\) is touched if scanned in original order), prepend \(a_q\) to \(P'\).
By maintaining a flag memorizing whether \(p\) has been appeared, for \(p=1,2,\dots,N\), this can be processed in a total of \(O(N)\) time. The array \(P'\) constructed this way consists of the elements touched at least once in the resulting \(P\). Appending this to \(P\) yields the desired array.

If we interpret the procedure as operating on \(P_1,P_2,\dots,P_N\) and then operating on \(a_1,a_2,\dots,a_Q\), all elements are touched at least once, so the former half process in this editorial can be omitted.