#include <stdio.h>

using namespace std;
FILE *f,*g;

int v[100002],n;

int caut(int val)
{
    int aux=-1,st,dr,mij;
    st=1;
    dr=n;
    mij=(st+dr)/2;
    while(st<=dr)
    {
        if(v[mij]>val)
            dr=mij-1;
        else
        {
            aux=mij;
            st=mij+1;
        }
        mij=(st+dr)/2;
    }
    return aux;
}

int caut1(int val)
{
    int aux=-1,st,dr,mij;
    st=1;
    dr=n;
    mij=(st+dr)/2;
    while(st<=dr)
    {
        if(v[mij]>=val)
            dr=mij-1;
        else
        {
            aux=mij;
            st=mij+1;
        }
        mij=(st+dr)/2;
    }
    return aux;
}



int main()
{
    int m,i,x,val,ss;
    f=fopen("cautbin.in","r");
    g=fopen("cautbin.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;++i)
        fscanf(f,"%d",&v[i]);
    fscanf(f,"%d",&m);
    for(i=1;i<=m;++i)
    {
        fscanf(f,"%d %d",&x,&val);
        if(x==2)
            ss=caut1(val);
        else
            ss=caut(val);
        if(v[ss]!=val)
        {
            if(x==0)
                fprintf(g,"-1\n");
            else
                if(x==1)
                    fprintf(g,"%d\n",ss);
                else
                    fprintf(g,"%d\n",ss+1);
        }
        else
            if(x==0 || x==1)
                fprintf(g,"%d\n",ss);
            else
                fprintf(g,"%d",ss+1);
    }
    fclose(f);
    fclose(g);
    return 0;
}