#include <fstream>

using namespace std;

int v[100002];

pair<int,bool> caut_bin(int n, int x) {
    int st=1, dr=n, mij;
    bool gasit=false;
    while(st<=dr && gasit==false) {
        mij=(st+dr)/2;
        if(v[mij]==x)
            gasit=true;
        else
            if(x<v[mij])
                dr=mij-1;
            else
                st=mij+1;
    }
    pair<int,bool> valoare_si_sukarime;
    valoare_si_sukarime.first=mij;
    valoare_si_sukarime.second=gasit;
    return valoare_si_sukarime;
}

int main()
{
    int n, x, i, poz, op, m,apartine_vector;
    pair<int,bool> valoare_si_sukarime2;
    ifstream in ("cautbin.in");
    ofstream out ("cautbin.out");
    in >> n;
    for(i=1; i<=n; ++i)
        in >> v[i];
    in >> m;
    while(m--) {
        in >> op >> x;
        if(op==0) {
            valoare_si_sukarime2=caut_bin(n,x);
            poz=valoare_si_sukarime2.first;
            apartine_vector=valoare_si_sukarime2.second;
            if(apartine_vector==0)
                out << -1 << endl;
            else {
                while(v[poz]==v[poz+1])
                    poz++;
                out << poz << endl;
            }
        }
        if(op==1) {
            valoare_si_sukarime2=caut_bin(n,x);
            poz=valoare_si_sukarime2.first;
            apartine_vector=valoare_si_sukarime2.second;
            if(apartine_vector==1) {
                while(v[poz]==v[poz+1])
                    poz++;
                out << poz << endl;
            }
            else
                out << v[poz];
        }
        if(op==2) {
            valoare_si_sukarime2=caut_bin(n,x);
            poz=valoare_si_sukarime2.first;
            apartine_vector=valoare_si_sukarime2.second;
            if(apartine_vector==1) {
                while(v[poz]==v[poz-1])
                    poz--;
                out << poz << endl;
            }
            else
                out << v[poz+1];
        }
    }
    in.close();
    out.close();
    return 0;
}