Problem D
Bogletics Intermission
Languages
en
is
Input
The first line of the input contains an integer $n$ satisfying $1 \leq n \leq 10^5$, the number of items that need to be placed in order. The next line contains $n$ integers $k_1, k_2, \dots , k_ n$ satisfying $1 \leq k_ i \leq n$. The value of $k_ i$ indicates in what location the item at location $i$ should be at the end. No $k_ i$ will take the value $n + 1$ as place $n + 1$ should always be empty at the beginning and end. All the $k_ i$ will be distinct.
Output
One line with an integer which gives the minimum number of moves to get the items to their desired locations.
Sample Input 1 | Sample Output 1 |
---|---|
4 1 3 2 4 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
8 7 4 6 8 1 3 5 2 |
11 |