#include<stdio.h>

int M,y,S,ifin,v[100010],jfin,w=1,max=-40000,N,o=1,x;

int caut1(int O)
{
    int st=1,dr=N,rez=-1,mid;

    while(st<=dr)
    {
    mid=(st+dr)/2;

            if(v[mid]==O)
            {
            rez=mid;
            st=mid+1;
            }
    if(v[mid]<O)
    st=mid+1;
    if(v[mid]>O)
    dr=mid-1;
    }

return rez;
}


int caut2(int O)
{
    int mid,st=1,dr=N,rez=-1;

    while(st<=dr)
    {
    mid=(st+dr)/2;

    if(v[mid]<=O)
    {
    rez=mid;
    st=mid+1;
    }
    if(v[mid]>O)
    dr=mid-1;
    }

return rez;
}


int caut3(int O)
{
    int mid,st=1,dr=N,rez=-1;

    while(st<=dr)
    {
    mid=(st+dr)/2;

    if(v[mid]<=O)
    {
    st=mid+1;
    }
    if(v[mid]>O)
    {
    rez=mid;
    dr=mid-1;
    }
    }
return rez;
}

int main()
{

freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);

scanf("%d",&N);

for(int i=1;i<=N;++i)
        scanf("%d",&v[i]);

    scanf("%d",&M);

    for(int i=1;i<=M;++i)
    {
        scanf("%d%d",&x,&y);
        if(x==0)
        printf("%d\n",caut1(y));
        if(x==1)
        printf("%d\n",caut2(y));
        if(x==2)
        printf("%d\n",caut3(y));
    }


return 0;
}