### Indian National Olympiad in Informatics

### Online Programming Contest, 10-11 September 2005

### Advanced Division

Problem 1: Book Sorting, *(K Narayan Kumar, CMI)*

Indraneel has to sort the books in his library. His library has
one long shelf. His books are numbered 1 through *N* and
he wants to rearrange the books so that they appear in the
sequece 1,2, ..., *N*.

He intends to do this by a sequence of moves. In each move he can
pick up any book from the shelf and insert it at a different
place in the shelf. Suppose Indraneel has 5 books and they are
initially arranged in the order

2 1 4 5 3

Indraneel will rearrange this in ascending order by first moving
book 1 to the beginning of the shelf to get

1 2 4 5 3

Then, moving book 3 to position 3, he gets

1 2 3 4 5

Your task is to write a program to help Indraneel determine the
minimum number of moves that are necessary to sort his book
shelf.

Input format

The first line of the input will contain a single integer
*N* indicating the number of books in Indraneel's
library. This is followed by a line containing a permutation of
1, 2, ..., *N* indicating the intial state of
Indraneel's book-shelf.

Output format

A single integer indicating the minimum number of moves necessary to
sort Indraneel's book-shelf.

Test Data:

You may assume that 1 ≤ *N* ≤ 200000. You may also
assume that in 50% of the inputs, 1 ≤ N ≤ 5000.

Example:

Here is the sample input and output corresponding to the example
discussed above.

Sample Input

5
2 1 4 5 3

Sample Output

2