#include<fstream>
#include<iostream>

using namespace std;

int a[100001],i,j,m,n,t,p,r,k,x,y;
int caut0(int y);
int caut1(int y);
int caut2(int y);

int main()
{
ifstream f("cautbin.in"); ofstream g("cautbin.out");
f>>n;
for(i=1;i<=n;i++) f>>a[i];
f>>m;
for(i=1;i<=m;i++)
{
 f>>x>>y;
 if(x==0)
 g<<caut0(y)<<"\n";
 if(x==1)
 g<<caut1(y)<<"\n";
 if(x==2)
 g<<caut2(y)<<"\n";
 
}


f.close(); g.close();
return 0;
}

int caut0(int y)
{ int m, i = 1;
  while(a[m] != y){
  m = (i+n)/2;
   if(a[m]>y) n = m;
   if(a[m]<y) i = m;
   if(a[m]==y) break;
  }
 while(a[m]==y)m++;
 return m-1;
 
}

int caut1(int y)
{ int m, i = 1;
  while(a[m] != y){
  m = (i+n)/2;
   if(a[m]>y) n = m;
   if(a[m]<y) i = m;
   if(a[m]==y) break;
  }
 while(a[m]==y)m++;
 return m-1;
 
}

int caut2(int y)
{ int m, i = 1;
  while(a[m] != y){
  m = (i+n)/2;
   if(a[m]>y) n = m;
   if(a[m]<y) i = m;
   if(a[m]==y) break;
  }
 while(a[m]==y)m--;
 return m+1;
 
}