#include <stdio.h>  
unsigned long a[100001];  
unsigned long x,y,n,l,m,i,ok;  
long bs(int x,long min,long max)  
{  
    int mij;  
    while (min<max){  
          mij=(min+max)/2;  
          if (a[mij]<x)min=mij+1;  
          else max=mij;  
          }  
    if (min<=n&&a[min]==x)  
       return min;  
    else {  
         ok=min;  
         return -1;  
         }  
}  
int main()  
{  
    freopen ("cautbin.in","r",stdin);  
    freopen ("cautbin.out","w",stdout);  
    scanf("%lu",&n);  
    for (i=1;i<=n;++i)  
        scanf("%lu ",&a[i]);  
    scanf("%lu",&m);  
    for (i=1;i<=m;++i){  
        scanf("%lu %lu",&x,&y);  
        if(x==0)printf("%lu\n",bs(y,1,n));  
        else if(x==1){  
             l=bs(y,1,n);  
             if(l==-1) printf("%lu\n",ok-1);  
             else printf("%lu\n",l);  
             }  
             else{  
             l=bs(y,1,n);  
             if(l==-1)printf("%lu\n",ok);  
             else printf("%lu\n",l);  
             }  
        }  
    return 0;  
}