#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define vi vector<int>
#define test int t; cin>>t; while(t--)
#define yn cout<<"YES\n"
#define nn cout<<"NO\n"
#define nl cout<<"\n"
#define fisier 1
const double PI=3.14159265359;
const int MOD = 1e9 + 7;
const int NMAX = 1e5;
int cb1(vector < int > v, int n, int x){
	int st = 1, dr = n, ans = -1;
	while (st < dr){
		int mid = st + (dr - st) / 2;
		if (v[mid] <= x)
			ans = mid,
			st = mid + 1;
		else
			dr = mid - 1;
	}
	return ans;
}
int cb2(vector < int > v, int n, int x){
	int st = 1, dr = n;
	while (st < dr){
		int mid = st + (dr - st) / 2;
		if (v[mid] >= x && v[mid - 1] < x) return mid;
		if (v[mid] < x) st = mid + 1;
		else dr = mid - 1;
	}
}
int32_t main(){
	#ifdef fisier
        ifstream cin("cautbin.in");
        ofstream cout("cautbin.out");
    #endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin >> n; vi v(n+1);
	for (int i = 1; i <= n; ++i) cin >> v[i];
	test {
		int a, b;
		cin >> a >> b;
		if (a == 0 || a == 1)
			cout << cb1(v,n,b), nl;
		else
			cout << cb2(v, n, b), nl;
	}	
}