cho.sh

The TA is a sadist!!

Given a permutation of 1 to N, find the minimum number of elements to remove so the remaining values increase from front to back.

Medium4Dynamic programmingBinary searchArraySortingInterviewNo attempts yetTime limit2sMemory limit256 MB

Problem

Heonwoo's class went on a school trip to Jeju Island. A teaching assistant in sunglasses was waiting outside the airport.

"Anyone who is not standing in order of student number had better be ready to get hit."

The assistant picks some of the students in the line and hits them. Once the students who were hit step out of the line, the numbers of the remaining students must increase from front to back. The assistant hits as few students as possible.

Given the number of students NN and their numbers in the order they currently stand, find how many students get hit.

Input

The first line contains the number of students NN. (1≤N≤200001 \le N \le 20000)

The second line contains the numbers of the NN students, separated by spaces, in the order they currently stand. Every number is between 11 and NN, and no number repeats.

Output

Print the number of students who get hit on the first line.