A Library at Home

Sanggeun bought many books to become the best in computer science. Since he has no bookshelf at home, the books are stacked in one pile.

Today Sanggeun is resting at home and wants to sort the pile by the lexicographic order of the book titles. The books are numbered from 1 to N in lexicographic order, and book 1 comes first. After sorting, reading the book numbers from top to bottom must give 1, 2, ..., N.

In one operation, he may take one book from anywhere in the current pile and place it on top of the pile. Given the current order of the books from top to bottom, compute the minimum number of operations needed to put the books in the correct order.

The first line contains the number of books N. N <= 300000.

Each of the next N lines contains a book number, listed from the top of the current pile to the bottom.

Print the minimum number of operations needed to sort the pile in lexicographic order.