\(P_i = 1\) なる \(i\) について、真っ先に、

• \(P_{i - 1} \) と \(P_i\) を入れ替える

• \(P_{i - 2} \) と \(P_{i - 1}\) を入れ替える

  \(\vdots\)

• \(P_{1} \) と \(P_{2}\) を入れ替える

という操作をしてしまって問題ありません。まず、この操作がこの順番で行われなければ、最終的に \(P_1 = 1\) とすることができません。また、入れ替える数に交わりのない操作は、行う順番を入れ替えても結果は変わらないことを考えると、操作を全て最初に行ってしまっても問題ないことが示せます。

この操作を行ったあと、 \(P_1, P_2, \ldots P_{i - 1}\) の値はその時点で確定します。よってこの中に \(P_j \neq j\) なる \(j\) があれば、答えは -1 です。そうでなければ、\(P_i\) 以降の部分について同様の議論を適用していけばよいです。

適切に実装することで、\(O(N)\) で問題を解くことができます。