#include<iostream>
#include<math.h>
#define FI "cautbin.in"
#define FO "cautbin.out"
using namespace std;

int V[100000],n;

int caz1(int x)
{
 int lo=0,hi=n-1;
 int m=((lo+hi)>>1);
 while (x!=V[m] && lo<hi)
 {
  if (V[m]>x) hi=m-1; else lo=m+1;
  m=((lo+hi)>>1);
 }
 return m;
}

int caz2(int x)
{
 int lo=0,hi=n-1;
 int m=((lo+hi)>>1);
 while (x!=V[m] && lo<hi)
 {
  if (V[m]>x) hi=m-1; else lo=m+1;
  m=((lo+hi)>>1);
 }
 return (x==V[m])?(m):(m+1);
}

int caz0(int x)
{
 int lo=0,hi=n-1;
 int m=((lo+hi)>>1);
 while(x!=V[m] && lo<hi)
 {
  if (V[m]>x) hi=m-1; else lo=m+1;
  m=((lo+hi)>>1);
 }
 while(lo<hi)
 {
  if (V[m]!=x) hi=m-1; else lo=m;
  m=((lo+hi)>>1);
 }
 return m;
}

int main()
{
 freopen(FI,"r",stdin);
 scanf("%d",&n);
 for(int i=0;i<n;++i)
  scanf("%d",V+i);
 p = (int) log2(n);
 int t,x,y,r;
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d",&x,&y);
  switch(x)
  {
    case 0: r=caz0(y);break;
    case 1: r=caz1(y);break;
    default r=caz2(y);break;
  }
  printf("%d\n",r);
 }

 fclose(stdin);
 fclose(stdout);
 return 0;
}