| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 98 | 26 | 16 | 23.188% |
Let's call sequence $b_1 , b_2 , \dots , b_m$ unfriendly, if the following condition holds:
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$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $a_i ≤ a_{i+1}$ |
| 2 | 6 | $n ≤ 8$ |
| 3 | 8 | The sum of $n$ over all test cases doesn't exceed 500ドル$ |
| 4 | 10 | $a_i ≤ 3$ |
| 5 | 10 | $a_i ≤ 10$ |
| 6 | 20 | The sum of $n$ over all test cases doesn't exceed 10000ドル$ |
| 7 | 43 | No additional constraints |
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
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)$.