[AdditionalFile3887.zip](file://AdditionalFile3887.zip?type=additional_file)

#3887. 「eJOI2022」Longest Unfriendly Subsequence

标签: 传统 | 时间限制: 1000 ms | 内存限制: 2048 MiB |

题目描述

本题译自 eJOI2022 Problem E. Longest Unfriendly Subsequence

我们称一个序列 $b_1,b_2,\ldots,b_m$ 是不友好的，如果它满足如下条件：

• 如果对于 $1\le i<j\le m$ 且 $j-i\le 2$，有 $b_i\neq b_j$。

换句话说，一个序列是不友好的，如果任意距离至多为 $2$ 的两个元素是不同的。

给定一个序列 $a_1,a_2,\ldots,a_n$，找到它最长不友好子序列的长度。

如果一个序列 $d$ 可以通过删除一些（可能不删，也可能删除全部）元素得到序列 $c$，则称序列 $c$ 是序列 $d$ 的子序列。例如 $(1,3,5)$ 是 $(1,2,3,4,5)$ 的一个子序列，而 $(3,1)$ 不是。

输入格式

第一行一个整数 $t\ (1\le t\le 10^5)$，表示测试点个数。每个测试点描述如下。

第一行包含一个整数 $n\ (1\le n\le 2\cdot 10^5)$，表示序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\le 10^9)$，表示序列 $a$。

保证一组测试数据中所有测试点的 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

对于每组测试点，输出一个整数，表示它最长不友好子序列的长度。

样例

输入

3
5
1 2 1 2 1
7
1 2 3 2 1 2 3
8
1 10 10 1 1 100 100 1

输出

2
6
4

第一个测试点中，最长不友好子序列是 $(1,2)$ 和 $(2,1)$。子序列 $(1,2,1)$ 不是不友好的，它第一个元素和第三个元素是相等的。

第二个测试点中，最长不友好子序列是 $(1,2,3,1,2,3)$。容易发现整个序列不是不友好的，所以答案是 $6$。

第三个测试点中，最长不友好子序列是 $(1,10,100,1)$。

评分

详细子任务附加限制及分值如下表所示。

注：$\sum n$ 指一组测试数据中所有测试点的 $n$ 的总和。