问题描述

给定一个长度为 $n$ 的整数序列 $a$，请你计算该序列的最长严格上升子序列的长度。

一个子序列是指从序列中删除若干个元素（也可以不删除）后剩下的元素按原顺序排列所构成的序列。严格递增子序列指子序列中的元素满足每个后继元素都比前面的元素大。

输入格式

第一行输入一个正整数 $n$，表示序列的长度。$(1 \leq n \leq 2 \times 10^5)$

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的数字。$(1 \leq a_i \leq 10^5)$

输出格式

输出一个正整数，表示该序列的最长严格上升子序列的长度。

样例输入

7
10 9 2 5 3 7 101

样例输出

4

提示

对于样例输入，最长严格上升子序列为 2 3 7 101，其长度为 4。