#include<fstream>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int main()
{  int i,ls,ld,m,ok=1,x,n,y;
   unsigned int v[100001];
   fin>>n;
   for(i=1;i<=n;i++)
	fin>>v[i];
   fin>>x;
   ls=0;
   ld=n-1;
   while(ok&&ls<=ld)
   {  m=(ld+ls)/2;
      if(x==v[m]) ok=0;
      else if(x>v[m]) ls=m+1;
           else ld=m-1;	  
   }
   n=m;
   while(v[m]==v[m-1]) m--;
   while(v[n]==v[n+1]) n++; 
   while(fin>>y>>x)
	 if(y==2) fout<<m<<endl;	 
	 else fout<<n<<endl;
    
  fin.close();
  fout.close();
  return 0;
}