#include <cstdio>
const int NMAX=100001;
int n,m,a[NMAX];
int s0(int x){
    int ls=1,ld=n,mij,r=-1;
    while (ls<=ld){
          mij=(ls+ld)/2;
          if (a[mij]==x) r=mij;
          if (a[mij]>x) ld=mij-1;
                  else ls=mij+1;
          }
    return r;
    } 
int s1(int x){
    if (a[n]==x) return n;
    int ls=1,ld=n,mij;
    while (ls<=ld){
          mij=(ls+ld)/2;
          if (a[mij]<=x && a[mij+1]>x) return mij;
          if (a[mij]<=x) ls=mij+1;
                  else ld=mij-1;
          }
    }  
int s2(int x){
    if (a[1]==x) return 1;
    int ls=1,ld=n,mij;
    while (ls<=ld){
          mij=(ls+ld)/2;
          if (a[mij]>=x && a[mij-1]<x) return mij;
          if (a[mij]<x) ls=mij+1;
                  else ld=mij-1;
          }
    }                      
int search(int o,int x){
    switch(o){
    case 0:return s0(x);
    case 1:return s1(x);
    case 2:return s2(x);
              }
    }
int main(){
    int x,op,i;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i) scanf("%d",&a[i]);
    for (scanf("%d",&m);m;m--){
        scanf("%d %d",&op,&x);
        printf("%d\n",search(op,x));
        }
    return 0;
}