| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 3 | 3 | 3 | 100.000% |
You have $n$ books arranged from left to right on a bookshelf. These books are uniquely labeled from 1ドル$ to $n$. The $i$-th book from the left is labeled $p_i$. You want to sort the books so that their labels are in ascending order from left to right.
In one step, you can perform one of the following actions:
Compute the minimum number of steps required to sort the books.
The first line of input contains an integer $n$ (2ドル ≤ n ≤ 500,円 000$). The second line contains $n$ pairwise distinct integers $p_1, p_2, \dots , p_n$ (1ドル ≤ p_i ≤ n$).
Output the minimum number of steps to sort the books in ascending order from left to right by their labels.
6 6 2 1 4 3 5
3
You can do the following three steps in order: swap the books labeled 2ドル$ and 1ドル,ドル swap the books labeled 4ドル$ and 3ドル,ドル and move the book labeled 6ドル$ to the rightmost position.
6 2 1 4 3 5 → 6 1 2 4 3 5 → 6 1 2 3 4 5 → 1 2 3 4 5 6
It can be shown that two or fewer steps are insufficient to sort the books.
9 9 2 4 3 7 5 1 8 6
5