题目描述

给定有 n 个数的 A 序列：A1, A2, A3, …, An。对于这个序列，我们想得到一个子序列 Ap1, Ap2, …, Api, …, Apm（1 ≤ p1 < p2 < … < pi < … < pm ≤ n），满足 Ap1 ≤ Ap2 ≤ … ≤ Api ≤ … ≤ Apm。从 A 序列最少删除多少元素，可以得到我们想要的子序列。

输入格式

第一行输入一个整数 n，代表 A 序列中数字的个数。（1 ≤ n ≤ 1000000）

第二个输入 n 个整数，代表 A1, A2, A3, …, An。（1 ≤ Ai ≤ 10000）

输出格式

输出最长不下降子序列。

输入样例 #1

8
2 1 5 3 6 4 6 3

输出样例 #1

4

输入样例 #2

6
1 2 2 3 3 5

输出样例 #2

6

输入样例 #3

8
9 8 7 6 5 5 1 1

输出样例 #3

2

数据范围与约定

1 ≤ n ≤ 1000000；1 ≤ Ai ≤ 10000。