#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

int cauta_ultima_aparitie(const vector<int>& v, int x) {
    int st=0; int dr = v.size()-1;
    int poz=-1;
    while(st<=dr) {
        int mid = st + (dr-st)/2;
        if (v[mid] == x) {
            poz = mid;
            st=mid+ 1;
        } else if (v[mid] < x) {
            st=mid-1;
        } else {
            dr=mid+1;
        }
    }

    return poz;
}

int cea_mai_mare_pozitie(const vector<int>& v, int x) {
    int st=0; int dr = v.size()-1;
    int poz=-1;
    while(st<=dr) {
        int mid = st + (dr-st)/2;
        if (v[mid] <= x) {
            poz = mid;
            st=mid+1;
        } else {
            dr=mid-1;
        }
    }

    return poz;
}

int cea_mai_mica_pozitie(const vector<int>&v, int x){
    int st=0; int dr = v.size()-1;
    int poz=-1;
    while(st<=dr) {
        int mid = st + (dr-st)/2;
        if (v[mid] >= x) {
            poz = mid;
            dr=mid-1;
        } else {
            st=mid+1;
        }
    }
    return poz;
}
int main(){
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    int N;
    fin>>N;
    vector<int> sir(N);
    for(int i=0; i<N; i++){
        fin>>sir[i];
    }

    int M;
    fin>>M;

    for(int i=0;i<=M;i++){
        int tip,x;
        fin>>tip>>x;
        if (tip==0){
            int rezultat = cauta_ultima_aparitie(sir,x);
            fout<<rezultat<<endl;
        }
        else if (tip==1){
            int rezultat = cea_mai_mare_pozitie(sir,x);
            fout<<rezultat<<endl;
        }
        else 
            {
                int rezultat = cea_mai_mica_pozitie(sir,x);
                fout<<rezultat<<endl;
            }
        }


    return 0;
    fin.close();
    fout.close();
}