#include<stdio.h>
#define N 100001
long binar2(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=0;step;step>>=1)
if(i+step<n&&v[i+step]<=y)
        i+=step;
if(v[i-1]>=y)
        return i-1;
else
        if(v[i]>=y)
                return i;
        else
                return i+1;}

long binar1(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=n;step;step>>=1)
if(i-step>1&&v[i-step]>=y)
        i-=step;
if(v[i]<=y)
        return i;
else
        return i-1;}

long binar0(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=0;step;step>>=1)
if(i+step<n&&v[i+step]<=y)
        i+=step;
if(v[i]==y)
      return i;
return -1;}

int main()
{long n,m,i,x,y,v[N];
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;i++)
       scanf("%ld",&v[i]);
scanf("%ld",&m);
for(i=1;i<=m;i++)
       {scanf("%ld%ld",&x,&y);
       if(x==0)
               if(v[n]==y)
                       printf("%ld\n",n);
               else
                       printf("%ld\n",binar0(v,n,y));
       else
               if(x==1)
                       if(v[n]<y)
                              printf("%ld\n",n);
                       else
                              printf("%ld\n",binar1(v,n,y));
               else
                       if(v[1]>y&&x==2)
                              printf("1\n");
                       else       
                              printf("%ld\n",binar2(v,n,y));}
fclose(stdin);
fclose(stdout);
return 0;}