#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) {
            fout << cauta_ultima_aparitie(sir, x) << "\n";
        } else if (tip == 1) {
            fout << cea_mai_mare_pozitie(sir, x) << "\n";
        } else {
            fout << cea_mai_mica_pozitie(sir, x) << "\n";
        }
    }

    return 0;

}