丈量走廊

能源分配完了，但Zero的核心是一个走廊——需要丈量长度。

"走廊？"CC问。

"对。"你说，"给定一个序列，找最长的递增子序列。"

"递增？"

"对。"你说，"每个数比前一个大。"

"子序列？"

"对。"你说，"不要求连续，但要求顺序。"

"咋找？"

"动态规划。"你说，"$dp[i]$表示以第$i$个数结尾的最长递增子序列长度。"

"转移？"

"枚举前面的数。"你说，"如果$a_j<a_i$，$dp[i]=\max(dp[i],dp[j]+1)$。"

"$O(n^2)$？"

"对。"你说，"但可以用二分优化到$O(n\log n)$。"

"二分？"

"对。"你说，"维护一个数组$d$，$d[len]$表示长度为$len$的递增子序列的最小结尾。"

"第47个数。"你说，"值为47——如果前面有46个数比它小，$dp[47]=47$。"

"最长？"

"对。"你说，"如果序列是$1,2,\dots,47$，最长递增子序列就是47。"

"如果乱序？"

"看具体值。"你说，"但总能找到一个最长的。"

CC看着走廊——像一条道，像一条河，像某种只能前进不能后退的路。

"走多远？"她问。

"看你能找到多长的递增序列。"你说，"每一步都要比前一步高。"

"像爬山？"

"对。"你说，"像爬山——每一步都要更高。"

"累了？"

"对。"你说，"但山顶的风景值得。"

Echo把递增子序列标记出来——像一串脚印，像一条上升的路。

"以前我走平地。"她说，"现在……在爬坡。"

"因为你在进步。"你说。

"对。"她说，"因为我在进步。"

题目描述

给定长度为$n$的序列，求最长严格递增子序列的长度。

输入格式

第一行$n$。第二行$n$个整数。

输出格式

最长严格递增子序列长度。

输入样例

5
1 2 3 4 5

输出样例

Oil : 9
2 1
3 1

提示

• $dp[i]$表示以$i$结尾的最长长度。
• 二分优化：维护$d[len]$为长度为$len$的最小结尾。
• 时间复杂度$O(n\log n)$。