26482번 - 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.

인터랙션 프로토콜

The contestant must implement one function with the following signature:

int solve(int N, int P[]);

solve will be called exactly once.

The function will be supplied with $N,ドル the number of toys, and $P,ドル an array (indexed from 0ドル$) containing the initial order of the toys. It has to return an int representing the minimum time required by Little Triangle to sort all the toys.

The sample grader reads the input from standard input with the following format:

• on the first line, the number $N$
• on the second line, the permutation $P$

The sample grader prints the result returned by solve to the standard output.

Attention! The contestant should not implement the main function.

입력

출력

제한

• 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.