#include<bits/stdc++.h>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main(){
	int n;
	in>>n;
	vector<int> a(n+1);
	a[0]=-1;
	for(int i=1;i<=n;i++) in>>a[i];
	int q;
	in>>q;
	while(q--){
        int t,x;
        in>>t>>x;
        if(t==0){
            int low=1,high=n,pos=-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(a[mid]==x){
                    pos=mid;
                    low=mid+1;
                }
                else if(a[mid]<x) low=mid+1;
                else high=mid-1;
            }
            out<<pos;
        }
        if(t==1){
            int low=1,high=n,pos=-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(a[mid]<=x){
                    low=mid+1;
                    pos=mid;
                }
                else high=mid-1;
            }
            out<<pos;
        }
        if(t==2){
            int low=1,high=n,pos=-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(a[mid]>=x){
                    high=mid-1;
                    pos=mid;
                }
                else low=mid+1;
            }
            out<<pos;
        }
        out<<'\n';
	}
}