#include <iostream>
#include <fstream>

using namespace std;

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

int a[100004], n;
int nr_intrebari;

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

int opt, x;

int cb_0 () {
    int l = 1, r = n;
    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;
    }
    return sol;

}

int cb_1 () {
    int l = 1, r = n;
    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;
            if(mij > sol)
                sol = mij;
        }

    }
    return sol;
}

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

    bool data = false;

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