#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("date.in");
ofstream out ("date.out");

int a[100004], n;
int nr_intrebari;

void citire() {
    in>>n;
    for(int i = 0; i < n ; i ++)
        in>>a[i];
    in>>nr_intrebari;
}

int opt, x;

int cb_0 () {
    int l = 0, r = n-1;
    int sol = -1;

    while (l <= r) {
        int mij = (l + r) / 2;
        if (a[mij] == x) {
            if(mij > sol)
                sol = mij;
            l = mij+1;
        }
        else if (a[mij] > x)
            r = mij - 1;
        else if (a[mij] < x)
            l = mij + 1;
    }
    sol++;
    return sol;

}

int cb_1 () {
    int l = 0, r = n-1;
    int sol = -1;

    while (l <= r){
        int mij = (l + r) / 2;
        if(a[mij] <= x){
            if(mij > sol){
                sol = mij;
            }
            l = mij+1;
        }
        else if (a[mij] > x)
            r = mij - 1;
        else
            l = mij + 1;
    }
    sol++;
    return sol;
}

int cb_2 () {
    int l = 0, r = n-1;
    int sol = -1;

    bool data = false;

    while (l <= r) {
        int mij = (l + r) / 2;
        if (a[mij] >= x) {
            if (!data){
                sol = mij;
                data = true;
            }
            if(mij < sol)
                sol = mij;
            l = mij + 1;
        }
        else if (a[mij] > x)
            r = mij - 1;
        else if (a[mij] < x)
            l = mij + 1;
    }
    sol;
    return sol;
}

void solve() {
    while (nr_intrebari) {
        in>>opt;
        in>>x;

        switch (opt) {
        case 0:
            out<<cb_0()<<"\n";
            break;
        case 1:
            out<<cb_1()<<"\n";
            break;
        case 2:
            out<<cb_2()<<"\n";
            break;
        }
        nr_intrebari--;
    }
}

int main() {
    citire();
    solve();
    return 0;
}