Crossing Out Numbers

Interview

Time limit1sMemory limit128 MB

Summary

Cross out as few numbers as possible so the numbers left behind read 1 to k in order.

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

Problem

Jasio wrote down a sequence of $n$ integers. We call a sequence a good sequence if it consists of the consecutive natural numbers $1, 2, 3, \dots$ starting from $1$ .

Jasio wants to cross out some of the numbers so that the ones that remain form a good sequence. The numbers that are left keep their original order (that is, they form a subsequence of the original sequence). Help him cross out as few numbers as possible.

If no good sequence can be formed in any way, then all of the numbers must be crossed out.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10^6$ ), the length of the sequence.

The second line contains the $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ), separated by spaces.

Output

Print a single line containing the minimum number of numbers Jasio must cross out.

Examples1

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