题目描述

After going downstairs of the literally Tower of White Jade, Youmu is on her way to the Human Village of Gensoukyo. When she came out of the Netherworld, she met the Phantom Ensemble who are on their way to have a music performance in the Netherworld.

After greatings with each other, the leader of the Phantom Ensemble Lunasa just asked Youmu a question about the number sequence.

Which is for a certain given positive number sequence, how many numbers should we delete so that after that we can confirm the sequence non-decreasing?

non-decreasing means for a certain positive integer sequence, every next element isn't less than the previous element.

In that way, she thinks the sequence is musical.

It is a easy question isn't it? Youmu just answered without thinking twice, which is just leaving one number in the sequence, because it must be non-decreasing.

But Merlin, the second leader of the Phantom Ensemble, just wants to test Youmu, so she changed the problem with just adding one more constraints, which is we need to delete the minimum number of elements of the sequence, so that the left sequence is non-decreasing.

Also, this is a easy problem for Youmu, she answered it quickly, can you answer it too?

picture:the Phantom Ensemble

输入格式

First line of the input contains one positive integer $N (1\\le N\\le10000)$ indicates the number of the positive integer sequence.

Then next line contains $N$ positive integers $a[i] (1\\le a[i]\\le10^9)$, the positive number sequence.

输出格式

The minimum number of elements needs deleting so that after that the sequence is non-decreasing.

样例

5 
1 2 3 1 3 

1

5 
2 2 2 2 2 

0

提示

In the first test case, we just remove the 1 at index 4, so the sequence becomes 1,2,3,3 it is non-decreasing. In the second test case, the original sequence is non-decreasing, so we don't need to delete any element.