#include <stdio.h>
#define nmax 100000
int a[nmax],n,t;
int i,x,y,val,mod;
int caut(int,int);

int main(){
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 
 scanf("%d",&n);
 for(i=0;i<n;++i)
    scanf("%d",&a[i]);
 scanf("%d",&t);
 for(;t;--t)
    {
    scanf("%d %d",&x,&y);    
    mod = x;
    val = y;
    printf("%d\n",caut(0,n-1)+1);
    } 
 
 return 0;
}

int caut(int start, int end){
    if(start==end)
        {
        if(!mod) return (a[start]==val)?start:-1;
        if(mod==1) return (a[start]>=val)?start-1:start;
        return (a[start]<=val)?start+1:start;
        }
    
    int mid = (start+end)/2;
    if(val <=a[mid]) return caut(start,mid);
    return caut(mid+1,end);
    
}