Subarray Sort

After spending winter break at his grandpa’s, Little Square returned home. While he was away, his friend, Little Triangle, played with his toys, numbered from $1$ to $N$. In order for Little Square not to be upset with him, Little Triangle has to put his toys back in order: $1, 2, \dots , N$.

Initially, all the toys are lined up on a shelf in some order.

Knowing that Little Triangle can sort a continuous interval $\[i, j]$ of toys in $\lfloor \sqrt{j-i+1} \rfloor$ seconds, help him find the minimum time he can order all the toys.

• $1 ≤ N ≤ 4 · 10^6$
• $\lfloor x \rfloor$ denotes the greatest integer $k ≤ x$.
• Each number between $1$ and $N$ will appear exactly once in $P$.
• The grader given to the contestants is not necessarily the same with the grader used for scoring.

In the first example, Little Triangle can sort the interval $\[0, 1]$ in $\lfloor \sqrt{1 - 0 + 1}\rfloor = \lfloor \sqrt{2} \rfloor = \lfloor 1.41421 \dots \rfloor = 1$ second. The permutation becomes $1$ $3$ $4$ $2$ $5$. He can now sort the interval $\[1, 3]$ in $\lfloor \sqrt{3-1+1} \rfloor = \lfloor \sqrt{3} \rfloor = \lfloor 1.73205 \dots \rfloor = 1$ second. The permutation becomes $1$ $2$ $3$ $4$ $5$. In total Little Triangle can sort all the toys in $1 + 1 = 2$ seconds, which is also the minimum possible time.

In the second example, the toys are already sorted.