#include<fstream>
using namespace std;

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

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