解题思路

新数组 $a'$ 是把原数组连续拼接了 $10^9+1$ 次得到的。

我们要求的是 $a'$ 的最长严格递增子序列长度。

先抓住两个关键点：

1. 原数组中每个元素满足 $1 \le a_i \le n$

题目内容

小美有一个长度为 $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$。

输出描述

对于每一组测试数据，新起一行，输出一个整数，表示新数组的最长严格递增子序列长度。

样例1

输入

2
4
1 1 2 3
5
4 5 3 3 4

输出

3
3

说明

在这组测试数据中:

• 对于第 $1$ 组，最终最长严格递增子序列为 {$1,2,3$}