排队

内存限制: 128 MiB 时间限制: 1000 ms
输入文件: line.in 输出文件: line.out

题目描述

nn 个人站成一排,每个人手中都有一个编号

现在想让队列的编号满足单调不降或者单调不增,你可以修改任何人手中的编号,请问最少要修改多少个人的编号?

输入格式

输入文件名为 line.in

第一行一个整数 nn,表示人数;
下面一行 nn 个整数,依次表示 a1,a2,,ana_1, a_2, \ldots, a_n

输出格式

输出文件名为 line.out

第一行输出一个整数,表示最少要修改的编号的数量。

样例

样例输入 1

5
1
3
2
1
1

样例输出 1

1

样例解释 1

将第一个人的编号改为任意不小于 33 的数即可,此时形成一个单调不增的序列。

数据范围与提示

对于 30%30\% 的数据,满足 n20,1ai5n\le 20, 1\le a_i\le 5
对于 50%50\% 的数据,满足 n2000n\le 2000
对于 100%100\% 的数据,满足 n100000n\le 100000
对于 100%100\% 的数据,满足 1ai1091\le a_i\le {10}^9