Cards in Place

Interview

Time limit1sMemory limit1024 MB

Summary

Given a row of cards with values, find the fewest cards to remove so the remaining cards read 1, 2, 3, ... from left to right.

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

Problem

$N$ cards are laid out in a row from left to right. The card at position $i$ from the left has the integer $A_i$ . ( $1 ≤ i ≤ N$ )

You may remove some of the $N$ cards. The order of the cards that remain is kept.

For example, let $N = 5$ and $A = [3, 1, 4, 1, 5]$ . If you remove the second and fifth cards, the remaining numbers from left to right are $3, 4, 1$ . So the number on the third remaining card from the left is $1$ .

After removing some cards, a remaining card is called a fixed card if the number on the $x$ -th remaining card from the left is exactly $x$ . If every remaining card is a fixed card, the arrangement is in the fixed state.

For example, let $N = 8$ and $A = [6, 1, 2, 3, 2, 4, 5, 10]$ . If you remove the first, fifth, and eighth cards, the remaining numbers are $1, 2, 3, 4, 5$ in order. Every remaining card is a fixed card, so the arrangement is in the fixed state.

If $N = 6$ and $A = [3, 4, 6, 10, 2, 5]$ , the only way to reach the fixed state is to remove every card so that no cards remain.

Removing all cards always results in the fixed state.

Write a program that computes the minimum number of cards that must be removed to reach the fixed state.

Input

The first line contains an integer $N$ .

The second line contains $N$ integers $A_1, \dots, A_N$ in order.

Output

Print the answer on the first line.

Constraints

$1 ≤ N ≤ 250,000$
For every $i$ ( $1 ≤ i ≤ N$ ), $1 ≤ A_i ≤ 250,000$ .

Examples3

Example 1
Input
```
1
1
```
Expected output
```
0
```
Example 2
Input
```
8
6 1 2 3 2 4 5 10
```
Expected output
```
3
```
Example 3
Input
```
6
3 4 6 10 2 5
```
Expected output
```
6
```