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

题目链接：Problem - B - Codeforces

【题目】

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;
}