#include <stdio.h>
long a[100001];
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("%ld",&n);
    for (i=1;i<=n;++i)
        scanf("%ld ",&a[i]);
    scanf("%ld",&m);
    for (i=1;i<=m;++i){
        scanf("%ld %ld",&x,&y);
        if(x==0)printf("%ld\n",bs(y,0,n));
        else if(x==1){
             l=bs(y,0,n);
             if(l==-1) printf("%ld\n",ok-1);
             else printf("%ld\n",l);
             }
             else{
             l=bs(y,0,n);
             if(l==-1)printf("%ld\n",ok);
             else printf("%ld\n",l);
             }
        }
    return 0;
}