Sorting Books in a Library

Mirko has a family library with (n) books arranged sequentially in a narrow cabinet. Each book is labeled with a unique integer from (1) to (n) corresponding to its alphabetical order. His goal is to arrange the books so that when read from the top, the books are in increasing order ((1,2,\cdots,n)).

However, because it is easy to pull a book out of the cabinet but hard to insert it back except at the top, the only operation allowed is to remove a book from anywhere and place it at the top of the cabinet.

The task is to calculate the minimum number of moves required to sort the books in the desired order. The key observation is that if you look from the bottom upward, you may already have a sequence of books in order. Specifically, set (expected = n) and traverse the list from bottom to top, reducing (expected) by one each time you encounter the book with the current (expected) value. The final answer is the remaining value of (expected).

inputFormat

The first line contains an integer (n) ((1\le n\le 10^5)) representing the number of books.

The next (n) lines each contain one integer representing the label of a book in the current arrangement from top to bottom.

outputFormat

Output a single integer representing the minimum number of moves required to achieve the sorted order.

sample

3
3
2
1

2