题目描述

给定一个长度为 $n$ 的序列，第 $i$ 个位置的值为 $a_i$ 。

请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是严格递增的。

输入格式

第一行，一个整数 $n$，表示序列长度。

第二行有 $n$ 个整数，表示这个序列。

输出格式

一个整数，表示答案

6
1 2 4 1 3 4

4

数据规模与约定

$n \le 10^5,a_i\le 10^9$

$Subtask1$: $n\le 10^3 , a_i \le 10^9$, $20$ 分

$Subtask2$: $n\le 10^5, a_i \le 10^5$, $60$ 分

$Subtask3$: $n\le 10^5, a_i \le 10^9$, $20$ 分