Split Subarray Sort

You have a parameter $K$. Consider performing the following action on an array $A$ of length $N$ **exactly once**: - Choose an integer $M$ and then $M$ intervals $[L_1, R_1], [L_2, R_2], \ldots, [L_M, R_M]$ such that: - $1 \le L_i \le R_i \le N$ - $L_1 = 1$ and $R_M = N$ - $L_i = R_{i - 1} + 1$ for all $2 \le i \le M$ - $R_i - L_i + 1 \le K$ - For each $i = 1 \ldots M$, sort $A[