#include<fstream>
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
int A[100001],n,i,T,t,tip,v,poz;

int bs0(int st, int dr, int val)
{
    int mij=st+(dr-st)/2;
    if(st>=dr)
    {
        if(A[mij]>val)
            mij--;
        if(A[mij]==val)
            return mij;
        return -1;
    }
    if(A[mij]<=val)
    {
        return bs0(mij+1,dr,val);
    }
    else
    {
        return bs0(st,mij-1,val);
    }
}

int bs1(int st, int dr, int val)
{
    int mij=st+(dr-st)/2;
    if(st>=dr)
    {
        if(A[mij]>val)
            mij--;
        return mij;
    }
    if(A[mij]<=val)
    {
        return bs0(mij+1,dr,val);
    }
    else
    {
        return bs0(st,mij,val);
    }
}

int bs2(int st, int dr, int val)
{
    int mij=st+(dr-st)/2;
    if(st>=dr)
    {
        if(A[mij]<val)
            mij++;
        return mij;
    }
    if(A[mij]<val)
    {
        return bs0(mij,dr,val);
    }
    else
    {
        return bs0(st,mij-1,val);
    }
}

int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
    {
        fi>>A[i];
    }
    fi>>T;
    for(t=1; t<=T; t++)
    {
        fi>>tip>>v;
        if(tip==0)
            poz=bs0(1,n,v);
        if(tip==1)
            poz=bs1(1,n,v);
        if(tip==2)
            poz=bs2(1,n,v);
        fo<<poz<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}