# Codeforces Round #768 (Div. 2) B. Fun with Even Subarrays

### 【题目】

You are given an array aa of nn elements. You can apply the following operation to it any number of times:

• Select some subarray from aa of even size 2k2k that begins at position ll (1≤l≤l+2⋅k−1≤n, k≥1) and for each i between 0 and k−1 (inclusive), assign the value al+k+i to al+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.

### [Input]

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤2⋅10^4) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer nn (1≤n≤2⋅10^5) — the length of the array.

The second line of each test case consists of nn integers a1,a2,…,an (1≤ai≤n) — the elements of the array a.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅10^5.

### [Output]

Print tt 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.

### [Example]

input

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

output

``````0
1
1
2
0``````

### [Note]

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 a1:=a2, 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 a4:=a5, 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 a3:=a4, and the array becomes [4,2,3,3], then you can apply another operation with k=2 and l=1, set a1:=a3, a2:=a4, and the array becomes [3,3,3,3].

In the fifth test, there is only one element, therefore no operations are needed.

### 【AC代码】

``````#include <iostream>
using namespace std;
const int M=2e5+9;
int a[M];
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while (t--) {
int n,ans=0;
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i];
}
int i=n-1;
while (i>0) {
if (a[i]!=a[n]) {
ans++;
i=n-(n-i)*2;
} else i--;
}
cout<<ans<<endl;
}
return 0;
}``````

THE END