#include <fstream>
#define nmax 100001
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int a[nmax],n,m,q,x;

int cautbin0(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 cautbin1(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 cautbin2(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()
{ fin>>n;
  int i;
  for(i=1; i<=n; i++) fin>>a[i];
  fin>>m;
  for(i=1; i<=m; i++)
      { fin>>q>>x;
        if(q==0) fout<<cautbin0(x);
        if(q==1) fout<<cautbin1(x);
        if(q==2) fout<<cautbin2(x);
        fout<<"\n";
      }
    return 0;
}