P13785 [eJOI 2022] Longest Unfriendly Subsequence

Let's call sequence $b_1, b_2, \ldots, b_m$ **unfriendly**, if the following condition holds: - If $1 \leq i < j \leq m$ and $j - i \leq 2$, then $b_i \neq b_j$. In other words, a sequence is **unfriendly** if any two elements on the distance at most 2 are different. You are given a sequence $a_1, a_2, \ldots, a_n$. Find the length of its longest **unfriendly** subsequence. A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements. For example, $(1, 3, 5)$ is a subsequence of $(1, 2, 3, 4, 5)$ while $(3, 1)$ is not.

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) - the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) - the length of the sequence. The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) - the elements of the sequence $a$. It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

For each test case, output a single integer - the length of the longest unfriendly subsequence of $a$.

### Note In the first test case, the longest unfriendly subsequences are $(1, 2)$ and $(2, 1)$. The subsequence $(1, 2, 1)$, for example, is not unfriendly, as its 1-st and 3-rd elements are equal. In the second test case, the longest unfriendly subsequence is $(1, 2, 3, 1, 2, 3)$. It's clear that the subsequence which consists of the whole sequence is not unfriendly, so the answer is 6. In the third test case, the longest unfriendly subsequence is $(1, 10, 100, 1)$. ### Scoring 1. (3 points): $a_i \leq a_{i+1}$ 2. (6 points): $n \leq 8$ 3. (8 points): The sum of $n$ over all test cases doesn't exceed 500 4. (10 points): $a_i \leq 3$ 5. (10 points): $a_i \leq 10$ 6. (20 points): The sum of $n$ over all test cases doesn't exceed 10000 7. (43 points): No additional constraints