A Library at Home

Time limit1sMemory limit128 MB

Summary

Find the minimum number of top-moves needed so a pile of numbered books ends up sorted 1..N from top to bottom.

Level: Medium4 of 10
Topics: Greedy, Array
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
3
3
2
1
```
Expected output
```
2
```
Example 2
Input
```
4
1
3
4
2
```
Expected output
```
2
```