#include <fstream>

using namespace std;

FILE*fin=fopen("cautbin.in","r");
FILE*fout=fopen("cautbin.out","w");

int a[100001],n,x,m,c;

void cauta0(int x)
{
    int st=1,dr=n,poz=-1,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]==x){ poz=mij; st=mij+1;}
        else
            if(a[mij]<x)
                st=mij+1;
            else
                dr=mij-1;
    }
    fprintf(fout,"%d\n",poz);
}

void cauta1(int x)
{
    int st=1,dr=n,poz,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x){ poz=mij; st=mij+1;}
        else
            dr=mij-1;
    }
    fprintf(fout,"%d\n",poz);
}
void cauta2(int x)
{
    int st=1,dr=n,poz,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]>=x){ poz=mij; dr=mij-1;}
        else
            st=mij+1;
    }
    fprintf(fout,"%d\n",poz);
}

int main()
{
    int i;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d ",&a[i]);
    fscanf(fin,"%d",&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d %d",&c,&x);
        if(c==0)    cauta0(x);
        else
            if(c==1)    cauta1(x);
            else    cauta2(x);
    }


    return 0;
}