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≤n1≤l≤l+2?k?1≤n, k≥1k≥1) and for each ii between 00 and k?1k?1 (inclusive), assign the value al+k+ial+k+i to al+ial+i.
For example, if a=[2,1,3,4,5,3]a=[2,1,3,4,5,3], then choose l=1l=1 and k=2k=2, applying this operation the array will become a=[3,4,3,4,5,3]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?1041≤t≤2?104) — 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?1051≤n≤2?105) — the length of the array.
The second line of each test case consists of nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n) — the elements of the array aa.
It is guaranteed that the sum of nn over all test cases does not exceed 2?1052?105.
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.
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
思路：一开始想着的是找到最长相同字序列然后不断操作，后面建了几次数据都感觉有问题。后面发现直接倒序往前操作就好了。因为每次只能往左边翻，那么如果一开始不是从最右边翻起，那么最后都需要再次去解决后面的问题。所以只要从右边开始，相同的有多少个，然后不断的往左翻，每次都能增加一倍的覆盖面积。
#include<iostream>
#include<bits/stdc++.h>
#define ll long long
#include<algorithm>
using namespace std;int n;
int a[200008];int main()
{int N;cin >> N;while(N--){cin >> n;for(int i=1;i<=n;i++)cin >> a[i];if(n==1){cout<<0<<endl;continue;}int key=1;int cnt=0;for(int i=n-1;i>=1;i--){if(a[i]==a[n]){key++;}else{cnt++;i=i-key+1;key*=2;} }cout<<cnt<<endl;} return 0;
}