lis

时间限制：1s 空间限制：1G 输入文件名：lis.in 输出文件名：lis.out

题目描述

花花和啾啾是好朋友。花花想送给啾啾一个序列，可是啾啾不喜欢递增子序列（lis）太长的序列。

可惜花花现在只有一个长度为 $n$ 的序列 $a_i$。于是花花不得已只能保留一个 $a$ 的子序列送给啾啾。为了表达诚意，保留后的序列的 lis 必须比原序列的 lis 小。

花花想问问你，他最长可以保留多长的序列呢？

输入格式

第一行输入一个正整数 $n$。 第二行输入 $n$ 个正整数 $a_i$。

输出格式

一个整数即为保留最长的序列的长度。

样例输入1

6
4 6 5 2 1 3

样例输出1

4

样例输入2

4
4 3 2 1

样例输出2

0

样例输入3

20
17 14 11 10 13 16 12 6 4 3 19 9 2 18 15 1 20 5 8 7

样例输出3

19

样例4/5在这里!

数据范围

$n \le 10^6, 1\le a_i \le 10^9$。