#include <stdio.h>

int v[100100];
int i,N,M,x,y;

inline int BS(int x,int L,int R)
{
    int M=L+(R-L)/2;

    if(L<=R)
    {
        if(x>=v[M]) return BS(x,M+1,R);
        else
        return BS(x,L,M-1);
    }
    else
    if(x==v[R]) return R;
    else return -1;
}

inline int BS1(int x,int L,int R)
{
    int M=L+(R-L)/2;

    if(L<=R)
    {
        if(x<v[M]) return BS1(x,L,M-1);
        else
        return BS1(x,M+1,R);
    }
    else return R;
}

inline int BS2(int x,int L,int R)
{
    int M=L+(R-L)/2;

    if(L<=R)
    {
        if(x<=v[M]) return BS2(x,L,M-1);
        else
        return BS2(x,M+1,R);
    }
    else return L;
}

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

    scanf("%d",&N);

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

    scanf("%d",&M);

    for(i=1;i<=M;i++)
    {
        scanf("%d%d",&x,&y);

        if(x==0) printf("%d\n",BS(y,1,N));
        else
        if(x==1) printf("%d\n",BS1(y,1,N));
        else
        printf("%d\n",BS2(y,1,N));
    }

    return 0;
}