#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]){
                    rg=mid-1;
                    poz=mid+1;
                }
                else
                    lf=mid+1;
            }
            fout << poz << 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;
        }
    }
}