题目描述

在拿到了上次的测试数据后，希蒙觉得不满意，要取到更多的样本才行，他决定派UN小赛码促进会全体成员作为敢死队去检测这部分的温度，不幸的是此次行动导致了他们的全军覆没，不过还在他们最后成功传回了数据，希蒙开开心心的拿到了数据，这次的温度依然没有一次是重复的！，现在他需要处理的就是，找出这段温度中，最长的上升子序列才行。 例如 $13，7，9，16，38，24，37，18，44，19，21，22，63，15$。 例中 $13，16，18，19，21，22，63$ 就是一个长度为 $7$ 的上升序列，同时也有 $7 ，9，16，18，19，21，22，63$ 组成的长度为 $8$ 的上升序列。

输入格式

第一行一个整数𝑛𝑛(1 <= 𝑛 <= 1000000) 第二行为 𝑛 个空格隔开的整数。

输出格式

最长上升子序列的长度。

样例

输入样例

10
3 18 7 14 10 12 23 41 16 24

输出样例

6

数据范围与提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 1000000$。。