Since each operation sorts a significant portion of the array, it is expected that the entire array can be sorted with a few operations. In fact:

• Perform the operation with \(k=1\). This sorts the entire array if \(P_1=1\) in the initial state. Otherwise, we have \(P_N \neq 1\) after the operation since \(N \geq 3\).

• Next, perform the operation with \(k=N\). Since \(P_N \neq 1\) before the operation, we have \(P_1=1\) after the operation.

• Perform the operation with \(k=1\). Since \(P_1=1\) before the operation, the entire array is certainly sorted after the operation.

By performing the above, any permutation can be sorted in at most three operations. Therefore, it is sufficient to quickly determine if the array can be sorted in zero, one, or two operations.

The determination for zero operations is trivial.

For the determination for one operation, if we fix \(k\), it is necessary and sufficient that the minimum and maximum values of \((P_1, P_2, \dots, P_{k-1})\) are \(1\) and \(k-1\), respectively, and \(P_k=k\). This can be checked in \(O(1)\) time for each \(k\) by taking cumulative \(\min\) and \(\max\), so the overall determination can be done in \(O(N)\) time.

Finally, for the determination for two operations, if \(P_N \neq 1\), it can be seen that starting from the second of the above three operations, the array can be sorted in two operations. Similarly, if \(P_1 \neq N\), it can be sorted in two operations. Conversely, if \(P_1=N\) and \(P_N=1\), the relative positions of \(1\) and \(N\) in \(P\) do not change with one operation, and they remain in the order \(N, 1\), clearly not satisfying the condition for sorting in one operation. Therefore,

\(P\) can be sorted in two or fewer operations \(\iff\) \(P_1 \neq N\) or \(P_N \neq 1\).

This can be checked in \(O(1)\) time.

From the above, the answer for each test case can be found in \(O(N)\) time.