小美有一个长度为 n 的数组 a_1,a_2,...,a_n ，她为了研究这个数组做出了个大胆的决定。现在，将与初始数组完全相同的数组连续拼接到其末尾，共拼接 10^9 次。设拼接完成后的新数组记为 a' ，则新数组的长度为 n × (10^9+1) ，并且对于任意的 n < i ≤ n × (10^9+1) ，都有 a'_i = a'_i-n 。 请你计算新数组 a' 的最长严格递增子序列的长度，并输出这个长度。 【名词解释】 子序列：从原序列中删除任意个（可以为零、可以为全部）元素后按原相对顺序得到的新序列。 严格递增子序列：子序列中相邻元素的值严格递增，即若子序列为 b_1,b_2,...,b_k ，则对所有 1≤ i<k ，都有 b_i<b_i+1 。
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤ T≤ 10^4) 代表数据组数，每组测试数据描述如下： 第一行输入一个整数 n(1≤ n≤ 2× 10^5) ，表示原数组的长度； 第二行输入 n 个整数 a_1,a_2,...,a_n(1≤ a_i≤ n) ，表示原数组的元素。 除此之外，保证单个测试文件的 n 之和不超过 2 × 10^5 。
对于每一组测试数据，新起一行，输出一个整数，表示新数组的最长严格递增子序列长度。
2 4 1 1 2 3 5 4 5 3 3 4
3 3
考点：动态规划
数据规模 n ≤ 200000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
参考方向：动态规划
把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。
思路框架（动态规划 通法 · 非本题专属）
实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。
复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例 1：输入 2 / 4 / 1 1 2 3 / 5 / 4 5 3 3 4 → 输出 3 / 3
在这组测试数据中：
对于第 1 组，最终最长严格递增子序列为 \1,2,3
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2026年春招-美团-技术岗-第二批笔试；2026年春招-美团-测试岗-第二批笔试；2026年春招-美团-硬件开发岗-第二批笔试 等。