cf-900-div3.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long

bool isValid(vector<vector<ll>> &store,ll l, ll r, ll k, ll x){
	ll count = r-l+1;
    ll res=0;
	for(int i=0;i<31;i++){
		ll val = store[r+1][i]-store[l][i];
		if(val>=count){
			res=res+(1<<i);
		}
	}
    if(res>=k){
        return true;
    }
	return false;
}

ll getValidR(vector<vector<ll>> &store,ll l, ll k, ll x){
	ll low=l;
	ll high=x-1;
	ll ans=-1;
	while(low<=high){
		ll mid = low + (high-low)/2;
		if(isValid(store,l,mid,k,x)){
            low=mid+1;
			ans=max(ans,mid);
		}
		else{
			high=mid-1;
		}
	}
    if(ans!=-1){
        ans++;
    }
	return ans;
}

void solve(){
	ll x;
	cin>>x;
	vector<ll>v(x);
	for(int i=0;i<x;i++){
		cin>>v[i];
	}
	vector<vector<ll>> store(x+1, vector<ll>(32,0));
	for(int i=0;i<x;i++){
		int val=v[i];
		int c=0;
        for(int j=0;j<32;j++){
            store[i+1][j]+=store[i][j];
        }
		while(val>0){
			int mod=val%2;
			val=val/2;
			store[i+1][c]+=mod;
			c++;
		}
	}
	ll q;
	cin>>q;
	while(q--){
		ll l,k;
		cin>>l>>k;
		l--;
		cout<<getValidR(store,l,k,x)<<" ";
	}
	cout<<endl;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}