P094 最长递增子序列

题目描述

给定 n 个整数 a1, \dots, an，求严格递增子序列的最长长度（LIS）。

子序列不要求连续。

输入格式

第一行 n（1 \le n \le 10^5）。
第二行 n 个整数 ai（|ai| \le 10^9）。

输出格式

LIS 长度。

样例

输入:
8
10 9 2 5 3 7 101 18

输出: 4