#include <cstdio>

using namespace std;

int N,M,v[100001],p,x;

int cautbin0(int fx,int lx,int x)
{
    int f=fx;
    int l=lx;

    while(l-f>1)
    {
        int m=(f+l)>>1;
        if(x<v[m])
            l=m-1;
        else f=m;
    }
    if(v[l]==x)return l;
    else if(v[f]==x)return f;
    else return -1;
}

int cautbin1(int fx,int lx,int x)
{
    int f=fx;
    int l=lx;

    while(l-f>1)
    {
        int m=(f+l)>>1;
        if(x<v[m])l=m-1;
        else f=m;
    }
    if(v[l]<=x)return l;
    else if(v[f]<=x)return f;
}


int cautbin2(int fx,int lx,int x)
{
    int f=fx;
    int l=lx;

    while(l-f>1)
    {
        int m=(f+l)>>1;
        if(v[m]<x)f=m+1;
        else l=m;
    }
    if(v[f]>=x)return f;
    else if(v[l]>=x)return l;
}

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",&p,&x);
        int c=0;
        if(p==0)c=cautbin0(1,N,x);
        else if(p==1)c=cautbin1(1,N,x);
        else if(p==2)c=cautbin2(1,N,x);

        printf("%d \n",c);
    }

    return 0;
}