#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;
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;
		int st = 1, dr = n, ans;
		if (a == 0 || a == 1){
			while (st <= dr){
				int mid = st + (dr - st) / 2;
				if (v[mid] <= b)
					ans = mid, st = mid + 1;
				else dr = mid - 1;
			}
			if (a == 1){
				if (v[ans] != b) cout << -1;
				else cout << ans, nl;
			}
			else
			cout << ans, nl;
		}
		else {
			while (st <= dr){
				int mid = st + (dr - st) / 2;
				if (v[mid] >= b)
					ans = mid, dr = mid - 1;
				else st = mid + 1;
			}
			cout << ans, nl;
		}
	}	
}