#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,i,j,k,in,a,b,sf,mij,v[100001];
int main()
{   f>>n;
    for (i=1;i<=n;++i)
        f>>v[i];
    f>>k;
    for (i=1;i<=k;++i) {
        f>>a>>b;
        if (a==0) {
            in=1;
            sf=n;
            while (in<=sf) {
                mij=(in+sf)/2;
                if (v[mij]<=b)
                    in=mij+1;
                else
                    sf=mij-1;}
            mij=(in+sf)/2;
            if (v[mij]>b)
                --mij;
            if (v[mij]==b)
                g<<mij<<'\n';
            else
                g<<-1<<'\n';}

        else if (a==1) {
            in=1;
            sf=n;
            while (in<sf) {
                mij=(in+sf)/2;
                if (v[mij]<=b)
                    in=mij+1;
                else
                    sf=mij;}
            mij=(in+sf)/2;
            if (v[mij]>b)
                --mij;
            g<<mij<<'\n';}

        else {
            in=1;
            sf=n;
            while (in<sf) {
                mij=(in+sf)/2;
                if (v[mij]<b)
                    in=mij+1;
                else
                    sf=mij;}
            mij=(in+sf)/2;
            if (v[mij]<b)
                ++mij;
            g<<mij<<'\n';}





    }

    return 0;
}