P13781 [eJOI 2022] Adjacent Pairs

Let's call an array $b_1, b_2, \ldots, b_m$ **good**, if $b_i \neq b_{i+1}$ for any $i$ with $1 \leq i \leq m - 1$. You are given a **good** array of $n$ positive integers $a_1, a_2, a_3, \ldots, a_n$. You can perform the following operations on this array: - Choose any index $i$ ($1 \leq i \leq n$) and a number $x$ ($1 \leq x \leq 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.

The first line of input contains the 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$ ($2 \leq n \leq 2 \cdot 10^5$) - the length of the array. The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) - elements of the array. It's guaranteed that $a_i \neq a_{i+1}$ for $1 \leq i \leq n - 1$ (that is, the array is **good**). It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

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.

### Note In the first test case, one of the optimal sequences of operations is: $(4, 5, 2, 4, 5) \rightarrow (2, 5, 2, 4, 5) \rightarrow (2, 5, 2, 4, 2) \rightarrow (2, 5, 2, 5, 2)$. In the second test case, the array already contains only two distinct values, so the answer is $0$. ### Scoring 1. (20 points): The sum of $n$ over all test cases does not exceed $100$ 2. (10 points): The sum of $n$ over all test cases does not exceed $500$ 3. (25 points): The sum of $n$ over all test cases does not exceed $4000$ 4. (45 points): No additional constraints