#include <cstdio>
int n,m;
int a[100030];
int cautbin2(int n,int val)
{
    int baza=0,nrr=1;
    while(n>nrr) nrr*=2;
    for(;nrr!=0;nrr>>=1)
    {
        int index=baza+nrr;
        if(index<=n)
        {
            if(a[index]<val)
            {
                baza=index;
            }
        }
    }
    return baza;
}
int cautbin(int n,int val)
{
    int baza=0,nrr=1;
    while(n>nrr) nrr*=2;
    for(;nrr!=0;nrr>>=1)
    {
        int index=baza+nrr;
        if(index<=n)
        {
            if(a[index]<=val)
            {
                baza=index;
            }
        }
    }
    return baza;
}
int main()
{
    freopen ("cautbin.in","r",stdin);
    freopen ("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    int tip,x;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&tip,&x);
        if(tip==0)
        {
            int pos=cautbin(n,x);
            if(a[pos]==x) printf("%d\n",pos);
            else printf("-1\n");
        }
        else if(tip==1)
        {
            int pos=cautbin(n,x);
            printf("%d\n",pos);
        }
        else
        {
            int pos=cautbin2(n,x);
            printf("%d\n",pos+1);
        }
    }
}