시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB5417825.000%

문제

Let's call sequence $b_1 , b_2 , \dots , b_m$ unfriendly, if the following condition holds:

  • If $1 ≤ i < j ≤ m$ and $j - i ≤ 2$, then $b_i ≠ 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 ,…, 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 ≤ t ≤ 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 ≤ n ≤ 2 ⋅ 10^5$) - the length of the sequence.

The second line of each test case contains $n$ integers $a_1 , a_2 , \dots , a_n$ ($1 ≤ a_i ≤ 10^9$) - the elements of the sequence $a$.

It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2 ⋅ 10^5$.

출력

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

서브태스크

번호배점제한
13

$a_i ≤ a_{i+1}$

26

$n ≤ 8$

38

The sum of $n$ over all test cases doesn't exceed $500$

410

$a_i ≤ 3$

510

$a_i ≤ 10$

620

The sum of $n$ over all test cases doesn't exceed $10000$

743

No additional constraints

예제 입력 1

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

예제 출력 1

2
6
4

힌트

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)$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.