시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB533320.000%

문제

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.

서브태스크

번호배점제한
17

$P$ is randomly generated.

28

$1 ≤ N ≤ 9$

335

$1 ≤ N ≤ 2000$

425

$1 ≤ N ≤ 100000$

525

No additional constraints.

예제 입력 1

5
3 1 4 2 5

예제 출력 1

2

예제 입력 2

3
1 2 3

예제 출력 2

0

힌트

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.

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.