block

Suppose a block boundary is placed after position $i$. After sorting and concatenating all blocks before that boundary, the result must equal the first $i$ elements of the fully sorted permutation. Therefore, $P_1,P_2,\cdots,P_i$ must consist of exactly $1,2,\cdots,i$.

Because all elements of a permutation are distinct, the following conditions are equivalent.

• $P_1,P_2,\cdots,P_i$ consists of exactly .

If the second condition holds, all first $i$ elements are at most $i$. Since they are $i$ distinct values, they must be exactly the integers from $1$ through $i$.

Scan the permutation from left to right while maintaining the prefix maximum. Place a boundary at every position $i$ where the prefix maximum equals $i$. Choosing all such boundaries is valid because the values between two consecutive boundaries form exactly the required consecutive value interval. Since every possible boundary is chosen, the number of blocks is maximum.

The time complexity is $O(N)$, and the additional space complexity is $O(1)$ when the input is processed as a stream.

Solution written by GPT5.6