Problem B
Bogletics Intermission

Image taken from commons.wikimedia.org
While they wait for the pizza from Trominos those that have already showed up pass the time by watching some shows. Since there weren’t a lot of suggestions Atli made a suggestion no one bothered to protest, so the end result is everyone watching Bogletics. At some point in the episode the main character runs into some problems. He has $n$ items and $n + 1$ places to store them. Since he can only carry so much and already has quite a few things on his person he can only carry one of these items at a time. Currently the items are distributed among the first $n$ places but not in the order he would like them to be. The only thing he can do is pick up an item and move it to an unoccupied place. How many trips does he have to make to get everything where he wants it to be?


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.


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
1 3 2 4
Sample Input 2 Sample Output 2
7 4 6 8 1 3 5 2

Please log in to submit a solution to this problem

Log in