Adjacent Pairs

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Let's call an array b_1, b_2, \dots , b_m good, if b_i \neq b_{i+1} for any i with 1 \le i \le m - 1.

You are given a good array of n positive integers a_1, a_2 , a_3 , \dots , a_n.

You can perform the following operations on this array:

  • Choose any index i (1 \le i \le n) and a number x (1 \le x \le 10^9). Then, set a_i to x. After this operation, the array has to remain good.

You want to perform several operations so that the resulting array will contain exactly two distinct values. Determine the smallest number of operations needed to achieve this goal.

Input Format

The first line of input contains the integer t (1 \le t \le 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 (2 \le n \le 2 \times 10^5) - the length of the array.

The second line of each test case contains n integers a_1 , a_2 , \dots , a_n (1 \le a_i \le n) - elements of the array. It's guaranteed that a_i \neq a_{i+1} for 1 \le i \le n - 1 (that is, the array is good).

It is guaranteed that the sum of n over all test cases does not exceed 2 \times 10^5.

Output Format

For each test case, output a single integer - the smallest number of operations needed to achieve an array in which there are exactly two distinct values.

Constraints

Subtask Points Additional constraints
1 20 The sum of n over all test cases does not exceed 100
2 10 The sum of n over all test cases does not exceed 500
3 25 The sum of n over all test cases does not exceed 4000
4 45 No additional constraints.

Sample Input

2
5
4 5 2 4 5
2
1 2

Sample Output

3
0

Explanation

In the first test case, one of the optimal sequences of operations is:

(4, 5, 2, 4, 5) → (2, 5, 2, 4, 5) → (2, 5, 2, 4, 2) → (2, 5, 2, 5, 2).

In the second test case, the array already contains only two distinct values, so the answer is 0.


Comments

There are no comments at the moment.