题目描述
本题译自 eJOI2022 Problem E. Longest Unfriendly Subsequence
我们称一个序列 b1,b2,…,bm 是不友好的,如果它满足如下条件:
- 如果对于 1≤i<j≤m 且 j−i≤2,有 bi=bj。
换句话说,一个序列是不友好的,如果任意距离至多为 2 的两个元素是不同的。
给定一个序列 a1,a2,…,an,找到它最长不友好子序列的长度。
如果一个序列 d 可以通过删除一些(可能不删,也可能删除全部)元素得到序列 c,则称序列 c 是序列 d 的子序列。例如 (1,3,5) 是 (1,2,3,4,5) 的一个子序列,而 (3,1) 不是。
输入格式
第一行一个整数 t (1≤t≤105),表示测试点个数。每个测试点描述如下。
第一行包含一个整数 n (1≤n≤2⋅105),表示序列的长度。
第二行 n 个整数 a1,a2,…,an (1≤ai≤109),表示序列 a。
保证一组测试数据中所有测试点的 n 的总和不超过 2⋅105。
输出格式
对于每组测试点,输出一个整数,表示它最长不友好子序列的长度。
评分
详细子任务附加限制及分值如下表所示。
子任务编号 |
附加限制 |
分值 |
1 |
ai≤ai+1 |
3 |
2 |
n≤8 |
6 |
3 |
∑n≤500 |
8 |
4 |
ai≤3 |
10 |
5 |
ai≤10 |
6 |
∑n≤104 |
20 |
7 |
无附加限制 |
43 |
注:∑n 指一组测试数据中所有测试点的 n 的总和。