提示: 欢迎访问OurACM平台。
Problem 1676 Christmas Trees

Accept: 86    Submit: 256
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Christmas is coming. So daxia should go to cut some Christmas trees. He has found N trees in a line and he calculated every tree’s height.
Now, he wanted to cut down the minimum trees to make the remaining M trees meeting the conditions (The N trees are numbered from 1 to N in the line and Hi is the i-th tree’s height):
H1 <= H2 <= ... <= Hj >= ... >= HM-1 >= HM.

Input

There are multiple test cases. For each test case, the first line contains an integer N(10≤N≤100000), indicating there are N trees. The second line has N 32-bit signed integers Hi (1≤i≤N), indicating the i-th tree’s height is Hi.

Output

For each test case, output an integer K, indicating he needs to cut down K trees at least.

Sample Input

10 1 2 3 4 5 4 3 2 1 2

Sample Output

1

Hint

We only need to cut down the last tree in the sample.

Source

FOJ月赛-2008年12月

Submit  Back  Status  Discuss