三（three）
题目描述
小 Y 手上有很多序列， 他希望能求出这些序列的最长子序列， 满足以下条件：
- 序列任意长度 $\leq 3$ 的子段中的元素互不相同。
如 $(1,2,3,4,5,6)$ 是合法的序列， 而 $(1,2,1)$ 不是合法的序列。
小 Y 希望你帮他求出他手上每个序列最长合法子序列的长度。
输入格式
第一行一个正整数 $t$， 表示序列个数。
每个序列表示如下：
第一行一个正整数 $n$， 表示序列的长度。
第二行 $n$ 个整数 $a_1,a_2,\cdots , a_n$， 表示这个序列。
输出格式
对于每个序列， 输出一个整数表示答案。
样例 #1
样例输入 #1
3
5
1 2 1 2 1
3
1 2 3
10
3 3 2 1 3 3 3 1 2 3样例输出 #1
2
3
5提示
对于 $100\%$ 的数据， 满足 $1\le n,\sum n\le 2\times10^5$， $1\le a_i\le 10^9$。
| 特殊性质 | 分值 | |
|---|---|---|
| $\operatorname{Subtask} 1$ | $a_i$ 单调不降 | $3$ |
| $\operatorname{Subtask} 2$ | $n\leq 8$ | $6$ |
| $\operatorname{Subtask} 3$ | $\sum n\leq 500$ | $8$ |
| $\operatorname{Subtask} 4$ | $a_i\leq 3$ | $10$ |
| $\operatorname{Subtask} 5$ | $a_i\leq 10$ | $10$ |
| $\operatorname{Subtask} 6$ | $\sum n\leq 10^4$ | $20$ |
| $\operatorname{Subtask} 7$ | 无 | $43$ |