#include <iostream>
#include <fstream>

using namespace std;

int v[100001], n;

int cautare_binara(int x, int t) {
    int st = 0, dr = n-1;
    int m;
    do {
        m = (st + dr)/2;
        if(v[m] == x) {
            while(v[m+1] == x && (t == 0 || t == 1))
                m++;
            while(v[m-1] == x && t == 2)
                m--;
            return m+1;
        }
        else if(x > v[m])
            st = m+1;
        else
            dr = m-1;
    } while(st <= dr);
    if(t == 1)
        if(v[m+1] < x) {
            while(v[m+1] < x) m++;
            return m+1;
        }
        else if(v[m-1] < x)
            return m-1;

    if(t == 2)
        if(v[m-1] > x) {
            while(v[m-1] > x) m--;
            return m-1;
        } else if(v[m+1] > x)
            return m+1;
    cout << m+1;
    return -1;
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> n;
    for(int i = 0; i < n; i++)
        fin >> v[i];
    int m, t, x;
    fin >> m;
    for(int i = 0; i < m; i++)
    {
        fin >> t >> x;
        fout << cautare_binara(x, t) << '\n';
    }
    cout << cautare_binara(3, 2);
    fin.close();
    fout.close();
    return 0;
}