#include <iostream>
#include <fstream>

using namespace std;


int pozitieMax(int start, int stop, int value, int values[]);


int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    long n, m;
    f>>n;
    int values[n+1];
    for (int i = 1; i <= n; ++i) {
        f>>values[i];
    }
    f>>m;
    while (m) {
        int type;
        //cout<<"\nQuery : \n";
        f>>type;
        int value;
        f>>value;
        if (type == 0) {
            int poz = pozitieMax(1, n,value, values);
            if (poz == -1) {
                g<<poz;
            } else {
                while(values[poz+1] == value) {
                    poz++;
                }
                g<<poz;
            }
        }
        else {
            int poz = pozitieMax(1, n, value, values);
            if (poz != - 1) {
                int p;
                if (type == 2) {
                    p = -1;
                } else {
                    p = 1;
                }
                while (values[poz + p] == value) {
                    poz = poz+p;
                }
                g<<poz;
            } else {
                if (type == 1) {
                    while (true) {
                        value = value-1;
                        int poz = pozitieMax(1, n, value, values);
                        if (poz != -1 ){
                            while (values[poz+1] == value) {
                                poz++;
                            }
                            g<<poz;
                            break;
                        }
                    }
                } else {
                    while(true) {
                        value++;
                        int poz = pozitieMax(1, n, value, values);
                        if (poz != -1) {
                            while (values[poz-1] == value) {
                                poz--;
                            }
                            g<<poz;
                            break;
                        }
                    }
                }
            }
        }
        g<<'\n';
        m--;
    }
    f.close();
    g.close();
    return 0;
}


int pozitieMax(int start, int stop, int value, int values[]){
    if (start > stop) {
        return -1;
    } else {
        int mid = (start + stop) / 2;
        if (values[mid] == value) {
            return mid;
        } else if (values[mid] < value) {
            return pozitieMax(mid+1, stop, value, values);
        } else {
            return pozitieMax(start, mid-1, value, values);
        }
    }

    return -1;


}