题目背景

气象台在连续 $n$ 天里记录了每天的平均气温。研究员想找出一段日子，使得这些日子的气温严格一天比一天高——日子不要求连续，但先后顺序不能打乱。这样的日子最多有多少天？

这就是经典的"最长上升子序列"问题。

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。

$a$ 的一个子序列是指：选取若干下标 $1 \le i_1 < i_2 < \dots < i_k \le n$，对应元素组成的序列 $a_{i_1},a_{i_2},\dots,a_{i_k}$。子序列中的元素在原序列中不要求连续。

若一个子序列满足

（严格递增，相等不算），则称它为一个严格最长上升子序列（Longest Increasing Subsequence，LIS）。

请求出严格最长上升子序列的长度。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

一行一个整数，表示严格最长上升子序列的长度。

样例

样例 1 输入

9
3 1 4 1 5 9 2 6 7

样例 1 输出

5

样例 1 解释

取第二个 1，再接 4 5 6 7，得到上升子序列 1 4 5 6 7，长度为 5。不存在长度为 6 的严格上升子序列。

样例 2 输入

10
2 2 1 1 2 2 3 3 4 4

样例 2 输出

4

样例 2 解释

序列中只有 4 种不同的值且大量重复。因为要求严格递增，相等的元素不能同时选取，答案是 4（例如 1 2 3 4），而不是 8 或 10。

样例 3 输入（稍大规模）

15
3 -1 2 -1 0 4 -3 2 5 1 4 6 0 5 7

样例 3 输出

6

样例 3 解释

序列包含负数和重复元素。答案为 6，例如取 -1 0 1 4 5 7（对应位置依次为第 2、5、10、11、14、15 个）；不存在长度为 7 的严格上升子序列。

数据范围与约定

• $1 \le n \le 2\times 10^5$
• $-10^9 \le a_i \le 10^9$（允许负数和 $0$，允许重复）

时间限制：1.0 秒，空间限制：256 MB。

提示

• 朴素动态规划：设 $f(i)$ 为以第 $i$ 个元素结尾的最长上升子序列长度，枚举前序位置转移，复杂度 $O(n^2)$，无法通过满规模数据。
• 更快的做法：维护数组 tails，其中 tails[k] 表示长度为 $k+1$ 的上升子序列的最小可能结尾值。对每个元素 $x$，用二分查找找到第一个 $\ge x$ 的位置并替换；若不存在则追加。答案为 tails 的长度，整体复杂度 $O(n\log n)$。
• 注意：严格递增必须使用"找第一个 $\ge x$"（lower_bound），这样遇到相等元素时只会替换而不会增长；若要求非严格递增，则应找第一个 $>x$（upper_bound）。