#include <cstdio>
#include <vector>

using namespace std;

int v[100002];

int _0(int li,int lf,int x)
{
    int m=li+(lf-li)/2;
    while (li<=lf)
    {
        if (v[m]<=x)
            li=m+1;
        else
            lf=m-1;
        m=li+(lf-li)/2;
    }
    if(lf<1)
        return -1;
    if(v[lf]==x)return lf;
    return -1;
}

int _1(int li,int lf,int x)
{
    int m=li+(lf-li)/2;
    while (li<=lf)
    {
        if (v[m]<=x)
            li=m+1;
        else
            lf=m-1;
        m=li+(lf-li)/2;
    }
    return lf;
}

int _2(int li,int lf,int x)
{
    int m=li+(lf-li)/2;
    while (li<=lf)
    {
        if (v[m]>=x)
            lf=m-1;
        else
            li=m+1;
        m=li+(lf-li)/2;
    }
    return m+1;
}

int main()
{
    FILE *f=fopen("cautbin.in","r");
    FILE *g=fopen("cautbin.out","w");
    int n,m,nr,x;
    fscanf(f,"%d",&n);
    int i;
    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",&nr,&x);
        if(nr==0) fprintf(g,"%d\n",_0(1,n,x));
        if(nr==1) fprintf(g,"%d\n",_1(1,n,x));
        if(nr==2) fprintf(g,"%d\n",_2(1,n,x));
    }
    return 0;
}