题目描述

给定有 n 个数的 A 序列：A1, A2, A3, …, An。对于这个序列，我们想得到一个子序列 Ap1, Ap2, …, Api, …, Apm（1 ≤ p1 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

3

输入样例 #2

6
1 2 2 3 3 5

输出样例 #2

1

输入样例 #3

8
9 8 7 6 5 5 1 1

输出样例 #3

6

数据范围与约定

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