We need to be able to sort a cycle of length \(k\) in \(k-1\) steps.

Let’s represent the cycle \(1 \to P_1 \to P_{P_1} \to \cdots \to 1\) as \(a_1,\cdots,a_k\).

We construct a Cartesian Tree of the sequence \(a=(a_1,\cdots,a_k)\). We make sure that the vertex with the smaller value is the parent. In particular, \(1\) is the root. For each \(i\), let \(p_i\) be the parent of \(i\). Then, we can see that if we perform the operation with \((l,r)=(a_{p_i},a_i)\) for \(i=k,k-1,\cdots,2\) in this order, all conditions will be satisfied.

The time complexity is \(O(N)\).

Sample Implementation