#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int main(){
    int n;
    fin >> n;
    long long v[n];
    for(int i=0;i<n;i++)
        fin >> v[i];
    int m;
    fin >> m;
    for(int i=0;i<m;i++){
        int cer,x;
        fin >> cer >> x;
        if(cer==0){
            int lf=0,rg=n-1;
            int poz=-1;
            while(lf<=rg){
                int mid=(lf+rg)/2;
                if(x==v[mid]){
                    poz=mid;
                    break;
                }
                if(x<v[mid])
                    rg=mid-1;
                else
                    lf=mid+1;
            }
            if(poz==-1)
                fout << poz << endl;
            else{
                if(v[poz]==v[n-1])
                    fout << n << endl;
                else {
                        int r=poz;
                        while (v[r]==v[poz])
                            r++;
                        fout << r << endl;
                }
            }
        }
        if(cer==1){
            int lf=0,rg=n-1;
            int poz=0;
            while(lf<=rg){
                int mid=(lf+rg)/2;
                if(v[mid]<=x){
                    poz=mid+1;
                    lf=mid+1;
                }
                else
                    rg=mid-1;
            }
            fout << poz << endl;
        }
        if(cer==2){
            int lf=0,rg=n-1;
            int poz=0;
            while(lf<=rg){
                int mid=(lf+rg)/2;
                if(v[mid]>=x){
                    poz=mid+1;
                    rg=mid-1;
                }
                else
                    lf=mid+1;
            }
            fout << poz << endl;
        }
    }
}