\(1\) 回の操作でもかなりの部分がソートされるので少ない回数の操作で全体をソートできることが期待されます。実際、

• \(k=1\) として操作を行う。 初期状態において \(P_1=1\) ならばこれで全体がソートされている。そうでない場合、 \(3 \leq N\) であるため、操作後は \(P_N\neq 1\) が成り立つ

• つづけて \(k=N\) として操作を行う。操作前では \(P_N\neq 1\) であるため、操作後 \(P_1=1\) が成り立つ

• \(k=1\) として操作を行う。操作前 \(P_1=1\) が成り立つので操作後必ず全体がソートされている

と操作を行うことで、どんな順列であっても \(3\) 回以下の操作でソートできます。よって \(0,1,2\) 回の操作で全体をソートできるかの判定が高速にできればいいです。

\(0\) 回でできるかの判定は明らかです。

\(1\) 回でできるかの判定については \(k\) を決め打って考えると \((P_1,P_2,\dots,P_{k-1})\) の最小値、最大値が \(1,k-1\) であり、 \(P_k=k\) が成り立つことが必要十分です。これは累積 \(\min,\max\) を取れば各 \(k\) に対し \(O(1)\) 時間で判定できるため、全体 \(O(N)\) 時間で判定できます。

最後に \(2\) 回でできるかの判定についてですが、 \(P_N \neq 1\) が成り立つ場合、上記の \(3\) 回の操作のうち \(2\) 回目の操作から始めることで \(2\) 回の操作でソート出来ることが分かります。 \(P_1\neq N\) の場合も同様に \(2\) 回の操作でできます。逆に \(P_1=N\) かつ \(P_N=1\) が成り立つ場合、 \(1\) 回の操作では \(P\) における \(1,N\) の位置関係は変わらず \(N,1\) の順で並んでおり、明らかに \(1\) 回の操作でソートできる条件を満たしません。よって

\(P\) が \(2\) 回以下の操作で全体をソートできる \(\iff\) \(P_1\neq N\) または \(P_N\neq 1\) を満たす

が成り立つことが分かり、これは \(O(1)\) 時間で判定できます。

以上より各テストケースについて \(O(N)\) 時間で答えを求めることができます。