#include<stdio.h>
long a[100000],n,i,m,f,r,x;
long cauta(long st,long dr,long x)
{long i,pas;
 for(pas=1;pas<dr;pas<<=1);
 for(i=0;pas;pas>>=1)
    if(i+pas<=dr&&a[i+pas]<=x)i+=pas;
 return i;
}
int main()
{
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;++i)scanf("%ld",&a[i]);
 a[i]=2000000000;
 scanf("%ld",&m);
 for(i=1;i<=m;++i)
    {scanf("%ld%ld",&f,&x);
     if(f==0)
       {
        r=cauta(1,n,x);
        if(a[r]!=x)r=-1;
        while(a[r+1]==x)
        {
        r=cauta(r,n,x);
        }
        printf("%ld\n",r);
       }
     if(f==1)
       {
        r=cauta(1,n,x);
        while(a[r-1]==x)
        {
        r=cauta(1,r,x);
        }
        if(a[r]<=x)++r;
        printf("%ld\n",r-1);
       }
     if(f==2)
       {
        r=cauta(1,n,x);
        while(a[r+1]==x)
        {
        r=cauta(r,n,x);
        }
        if(a[r]>=x)--r;
        printf("%ld\n",r+1);
       }
    }
 return 0;
}