#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
FILE *in=fopen("cautbin.in","r");
FILE *out=fopen("cautbin.out","w");
int a[100001];
 int search0(int s, int d, int x)
 {
     int m,f=-1;
     while(s<=d)
     {
                m=(s+d)/2;
                if(a[m]==x) f=m;
                if(a[m]>x) d=m-1;
                else s=m+1;
     }
     return f;
 }
 int search1(int s, int d, int x)
 {
     int m;
     if(a[d]==x) return d;
     while(s<=d)
     {
               m=(s+d)/2;
               if(x>=a[m] && x<a[m+1]) return m;
               if(x>=a[m]) s=m+1;
               else d=m-1;
     }
 }
 int search2(int s, int d, int x)
 {
     int m;
     if(a[1]==x) return 1;
     while(s<=d)
     {
               m=(s+d)/2;
               if(x<=a[m] && x>a[m-1]) return m;
               if(x>a[m]) s=m+1;
               else d=m-1;
     }
 }

     
int main()
{
    int n,nrc,c,r,poz;
    fscanf(in,"%d",&n);
    for(int i=1;i<=n;i++)
        fscanf(in,"%d",&a[i]);
    fscanf(in,"%d",&nrc);
    for(int i=0;i<nrc;i++)
    {
        fscanf(in,"%d%d",&c,&r);
        if(c==0) fprintf(out,"%d\n",search0(1,n,r));
        if(c==1) fprintf(out,"%d\n",search1(1,n,r));
        if(c==2) fprintf(out,"%d\n",search2(1,n,r));
    }
    fclose(in); fclose(out);
    return 0;
}