Copying items in arrays while checking their indexes
All you're looking for is some mapping between the elements of $P$ and their indexes, that can be found in $O(1)$ for each element of $P$. Suppose given $p_i \in P$, you can use the fact that $p_i \in \{0, \dots n-1\}$, and that no $p_j \in P$ exists s.t $p_j = p_i$ (other than $j=i$).

How will you do it? Set $R[x]$ to the index of element $x \in P$.


Since $x$ is unique, no elements of $R$ will be overridden.
Suppose $p_i , p_j \in P$, and $p_i$ occures before $p_j$ ($i&lt;j$). Then $R[p_i] = i$ and $R[p_j] = j$, and it holds that $R[p_i]&lt;R[p_j]$


You should be able to take it from here.