#include<stdio.h>
#include<conio.h>
#include<time.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]<y)
        return i+1;
return i;}

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>0&&v[i-step]>=y)
        i-=step;
if(v[i]>y)
        return i-1;
return i;}

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];
FILE *f1=fopen("cautbin.txt","r");
FILE *f2=fopen("cautbin2.txt","w");
clock_t t1,t2;
t1=clock();
fscanf(f1,"%ld",&n);
for(i=1;i<=n;i++)
       fscanf(f1,"%ld",&v[i]);
fscanf(f1,"%ld",&m);
for(i=1;i<=m;i++)
       {fscanf(f1,"%ld%ld",&x,&y);
       if(x==0)
               fprintf(f2,"%ld\n",binar0(v,n,y));
       else
               if(x==1)
                       fprintf(f2,"%ld\n",binar1(v,n,y));
               else
                       fprintf(f2,"%ld\n",binar2(v,n,y));}
t2=clock();
printf("%lf\n",(double)(t2-t1)/CLOCKS_PER_SEC);
fclose(f1);
fclose(f2);
getch();
return 0;}