311081: CF1931C. Make Equal Again

C. Make Equal Againtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have an array $a$ of $n$ integers.

You can no more than once apply the following operation: select three integers $i$, $j$, $x$ ($1 \le i \le j \le n$) and assign all elements of the array with indexes from $i$ to $j$ the value $x$. The price of this operation depends on the selected indices and is equal to $(j - i + 1)$ burles.

For example, the array is equal to $[1, 2, 3, 4, 5, 1]$. If we choose $i = 2, j = 4, x = 8$, then after applying this operation, the array will be equal to $[1, 8, 8, 8, 5, 1]$.

What is the least amount of burles you need to spend to make all the elements of the array equal?

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of input test cases. The descriptions of the test cases follow.

The first line of the description of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10 ^ 5$) — the size of the array.

The second line of the description of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — array elements.

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

Output

For each test case, output one integer — the minimum number of burles that will have to be spent to make all the elements of the array equal. It can be shown that this can always be done.

ExampleInput

8
6
1 2 3 4 5 1
7
1 1 1 1 1 1 1
8
8 8 8 1 2 8 8 8
1
1
2
1 2
3
1 2 3
7
4 3 2 7 1 1 3
9
9 9 2 9 2 5 5 5 3

Output

4
0
2
0
1
2
6
7

题目大意：
你有一个包含n个整数的数组a。你可以最多执行一次以下操作：选择三个整数i、j、x（1≤i≤j≤n），并将数组中从索引i到j的所有元素赋值为x。这个操作的费用取决于所选择的索引，并且等于(j-i+1)个单位。问：使数组中所有元素相等所需花费的最少单位是多少？

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——输入测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——数组的大小。
每个测试用例的第二行包含n个整数a1、a2、…、an（1≤ai≤n）——数组元素。
保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个整数——使数组中所有元素相等将需要花费的最少单位数。可以证明这总是可以做到的。

示例：
输入
8
6
1 2 3 4 5 1
7
1 1 1 1 1 1 1
8
8 8 8 1 2 8 8 8
1
1
2
1 2
3
1 2 3
7
4 3 2 7 1 1 3
9
9 9 2 9 2 5 5 5 3
输出
4
0
2
0
1
2
6
7

注意：以上内容中的"单位"在原文中是"burles"，这里为了理解方便，我将其翻译为"单位"。题目大意： 你有一个包含n个整数的数组a。你可以最多执行一次以下操作：选择三个整数i、j、x（1≤i≤j≤n），并将数组中从索引i到j的所有元素赋值为x。这个操作的费用取决于所选择的索引，并且等于(j-i+1)个单位。问：使数组中所有元素相等所需花费的最少单位是多少？ 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——输入测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——数组的大小。 每个测试用例的第二行包含n个整数a1、a2、…、an（1≤ai≤n）——数组元素。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数——使数组中所有元素相等将需要花费的最少单位数。可以证明这总是可以做到的。 示例： 输入 8 6 1 2 3 4 5 1 7 1 1 1 1 1 1 1 8 8 8 8 1 2 8 8 8 1 1 2 1 2 3 1 2 3 7 4 3 2 7 1 1 3 9 9 9 2 9 2 5 5 5 3 输出 4 0 2 0 1 2 6 7 注意：以上内容中的"单位"在原文中是"burles"，这里为了理解方便，我将其翻译为"单位"。