#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100001],n,m,q,x;
int cb0(int num)
{ int s=1,d=n;
  int pp=0;
  int val;
  while(s<=d && pp==0)
     { int m=(s+d)/2;
       if(a[m]==num) {val=m; pp=1;}
       else if(a[m]<num) s=m+1;
            else d=m-1;
     }
  while(a[val]==num) val++;
  return val-1;
}
int cb1(int num)
{ int s=1,d=n;
  int val;
  while(s<=d)
     { int m=(s+d)/2;
       if(a[m]<=num) {val=m; s=m+1;}
          else d=m-1;
     }
  return val;
}
int cb2(int num)
{ int s=1,d=n;
  int val;
  while(s<=d)
     { int m=(s+d)/2;
       if(a[m]>=num) {val=m; d=m-1;}
          else s=m+1;
     }
  return val;
}
int main()
{ f>>n;
  int i;
  for(i=1; i<=n; i++) f>>a[i];
  f>>m;
  for(i=1; i<=m; i++)
      { f>>q>>x;
        if(q==0) g<<cb0(x);
        if(q==1) g<<cb1(x);
        if(q==2) g<<cb2(x);
        g<<'\n';
      }
    return 0;
}