Line Up

Interview

Time limit1sMemory limit128 MB

Summary

Find the minimum number of children to move so the line ends in sorted order, equivalent to N minus the longest increasing subsequence length.

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

Problem

There are N children in a daycare, numbered from 1 to N. During a trip, the children should walk in one line in increasing order of their numbers, but their current order has become mixed.

In one move, the teacher chooses one child and moves that child to any position in the line. To avoid confusing the children, the teacher wants to move as few children as possible.

Given the current order of the N children, find the minimum number of children that must be moved so that the line becomes ordered from 1 to N.

Input

The first line contains the number of children N.

Each of the next N lines contains one integer from 1 to N, describing the current order of the children from front to back.

N is an integer between 2 and 200, inclusive, and each number from 1 to N appears exactly once.

Output

Print the minimum number of children that must be moved to arrange the line in increasing order of number.

Examples1

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