長さ \(k\) のサイクルを \(k-1\) 回でソートできれば良い．

サイクル \(1 \to P_1 \to P_{P_1} \to \cdots \to 1\) を \(a_1,\cdots,a_k\) と表す．

数列 \(a=(a_1,\cdots,a_k)\) の Cartesian Tree を作る． 値の小さい頂点が親になるようにする． 特に \(1\) が親． 各 \(i\) について \(i\) の親を \(p_i\) とおく． このとき，\(i=k,k-1,\cdots,2\) について，この順に \((l,r)=(a_{p_i},a_i)\) として操作を行えば，すべての条件を満たしていることが確認できる．

計算量は \(O(N)\) になる．

実装例