Unequal Array

题意翻译

您将获得一个长度为 $n$ 的数组 $a$。我们将数组的相等性定义为索引数 $1 \le i \le n - 1$ 使得 $a_i = a_{i + 1}$。我们可以执行以下操作： - 选择两个整数 $i$ 和 $x$，使得 $1 \le i \le n - 1$ 和 $1 \le x \le 10^9$。然后，将 $a_i$ 和 $a_{i + 1}$ 设置为 $x$ 。 找到所需的最小操作数，使数组的相等性 $\le1$ 。

题目描述

You are given an array $ a $ of length $ n $ . We define the equality of the array as the number of indices $ 1 \le i \le n - 1 $ such that $ a_i = a_{i + 1} $ . We are allowed to do the following operation: - Select two integers $ i $ and $ x $ such that $ 1 \le i \le n - 1 $ and $ 1 \le x \le 10^9 $ . Then, set $ a_i $ and $ a_{i + 1} $ to be equal to $ x $ . Find the minimum number of operations needed such that the equality of the array is less than or equal to $ 1 $ .

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 2 \le n \le 2 \cdot 10 ^ 5 $ ) — the length of array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10 ^ 5 $

输出格式

For each test case, print the minimum number of operations needed.

输入输出样例

输入样例 #1

4
5
1 1 1 1 1
5
2 1 1 1 2
6
1 1 2 3 3 4
6
1 2 1 4 5 4

输出样例 #1

2
1
2
0

说明

In the first test case, we can select $ i=2 $ and $ x=2 $ to form $ [1, 2, 2, 1, 1] $ . Then, we can select $ i=3 $ and $ x=3 $ to form $ [1, 2, 3, 3, 1] $ . In the second test case, we can select $ i=3 $ and $ x=100 $ to form $ [2, 1, 100, 100, 2] $ .