Fun with Even Subarrays

题意翻译

给定一个长度为 $n$ 的数据 $a$。你可以执行若干次操作，每次操作你可以选择一个位置 $i$ 和一个整数 $k$，但需要保证 $1\leqslant l\leqslant l+2\cdot k-1\leqslant n$，$k\geqslant 1$。然后对于所有的 $0\leqslant j\leqslant k-1$，将 $a_{i+j}$ 的值替换为 $a_{i+k+j}$。你希望最终得到一个所有元素的值相等的数组，求最小的操作次数。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 2\times 10^4$。 - $1\leqslant n,\sum n\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant n$。 Translated by Eason_AC 2022.1.28

题目描述

You are given an array $ a $ of $ n $ elements. You can apply the following operation to it any number of times: - Select some subarray from $ a $ of even size $ 2k $ that begins at position $ l $ ( $ 1\le l \le l+2\cdot{k}-1\le n $ , $ k \ge 1 $ ) and for each $ i $ between $ 0 $ and $ k-1 $ (inclusive), assign the value $ a_{l+k+i} $ to $ a_{l+i} $ . For example, if $ a = [2, 1, 3, 4, 5, 3] $ , then choose $ l = 1 $ and $ k = 2 $ , applying this operation the array will become $ a = [3, 4, 3, 4, 5, 3] $ . Find the minimum number of operations (possibly zero) needed to make all the elements of the array equal.

输入输出格式

输入格式

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

输出格式

Print $ t $ lines, each line containing the answer to the corresponding test case — the minimum number of operations needed to make equal all the elements of the array with the given operation.

输入输出样例

输入样例 #1

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

输出样例 #1

0
1
1
2
0

说明

In the first test, all elements are equal, therefore no operations are needed. In the second test, you can apply one operation with $ k=1 $ and $ l=1 $ , set $ a_1 := a_2 $ , and the array becomes $ [1, 1] $ with $ 1 $ operation. In the third test, you can apply one operation with $ k=1 $ and $ l=4 $ , set $ a_4 := a_5 $ , and the array becomes $ [4, 4, 4, 4, 4] $ . In the fourth test, you can apply one operation with $ k=1 $ and $ l=3 $ , set $ a_3 := a_4 $ , and the array becomes $ [4, 2, 3, 3] $ , then you can apply another operation with $ k=2 $ and $ l=1 $ , set $ a_1 := a_3 $ , $ a_2 := a_4 $ , and the array becomes $ [3, 3, 3, 3] $ . In the fifth test, there is only one element, therefore no operations are needed.