For the first subtask, any standard sorting algorithm is enough to score full points.

Number of operations: ~\mathcal O(N^2)~ or ~\mathcal O(N \log N)~

For the second subtask, observe that the permutation can be modelled as a graph. Build an "edge" from each element ~i~ to ~P_i~. After this is done, the permutation can be modelled as a set of disjoint cycles. Each shift operation performs a cyclic shift on some cycle so it takes exactly ~1~ operation to sort a cycle. Because we only need to perform a shift operation on cycles of size greater than ~1~, there are at most ~N/2~ such cycles. This is enough to score full points for the second subtask.

Number of operations: ~N/2~

For the final subtask, observe that the answer is always ~0~, ~1~, or ~2~.

If the permutation is initially sorted, the number of operations needed is ~0~.

If the permutation consists of exactly ~1~ cycle, the number of operations needed is ~1~.

Suppose the permutation consists of ~m \ge 2~ cycles. Let the cycles be ~a_1, a_2, \dots, a_m~ and their sizes be ~k_1, k_2, \dots, k_m~. Each cycle can be represented as ~[a_{i,1}, a_{i,2}, \dots, a_{i,k_i}]~.

The first shift operation is ~a_{1,1}, a_{1,2}, \dots, a_{1,k_1}, a_{2,1}, a_{2,2}, \dots, a_{2,k_2}, \dots, a_{m,k_m}~.

The second shift operation sorts each first element of each cycle after it was displaced in the first operation. So the second shift operation is ~a_{m,1}, a_{m-1,1}, \dots, a_{1,1}~.

Number of operations: ~0~, ~1~, or ~2~