#include <cstdio>
FILE *g=fopen("cautbin.in","r");
FILE *z=fopen("cautbin.out","w");
using namespace std;
int v[500000],n;
void binar0(int o)
{
    int down=1,high=n,t;
    while(down<=high)
    {
        t=(down+high)/2;
        if(v[t]<=o)
        down=t+1;
        else
        high=t-1;
    }
    t=(down+high)/2;
    if(v[t]>o)
    t--;
    if(v[t]==o)
    fprintf(z,"%d\n",t);
    else
    fprintf(z,"-1");
}
void binar1(int o)
{
    int down=1,high=n,t;
    while(down<high)
    {
        t=(down+high)/2;
        if(v[t]<=o)
        down=t+1;
        else
        high=t;
    }
    t=(down+high)/2;
    if(v[t]>o)
    --t;
    fprintf(z,"%d\n",t);
}
void binar2(int o)
{
    int down=1,high=n,t;
    while(down<high)
    {
        t=(down+high)/2;
        if(v[t]<o)
        down=t+1;
        else
        high=t;
    }
    t=(down+high)/2;
    if(v[t]<o)
    ++t;
    fprintf(z,"%d\n",t);
}
int main()
{
    int i,m,op,o;
    fscanf(g,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(g,"%d",&v[i]);
    fscanf(g,"%d",&m);
    for(i=1;i<=m;i++)
    {
        fscanf(g,"%d%d",&op,&o);
        if(op==0)
        binar0(o);
        else if(op==1)
        binar1(o);
        else
        binar2(o);

    }
    return 0;
}