#include<fstream>
#define dim 100001
using namespace std;
unsigned long a[dim],n,x;

unsigned long binary_search(unsigned long x)
      {unsigned long i,step;
	   for(step=1;step<n;step<<=1);
	   for(i=0;step;step>>=1)
	      if(i+step<n&&a[i+step]<=x)
			  i+=step;
		return i;  
       }
 int main()
    {unsigned long h,y,m,i;
	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>>h>>x;
	      if(h==0) {y=binary_search(x);
		    /*if(a[y]!=x)g<<-1<<'\n';
		      else if((y==1)&&(a[1]==x))g<<y<<'\n';
		      else if(a[n]==x)g<<n<<'\n';
		       else g<<y<<'\n';} */
		   if(a[1]==x)g<<y<<'\n'; 
		    else if(a[y]!=x)g<<-1<<'\n';
		      else g<<y<<'\n';}
		  
		  else if(h==1) {y=binary_search(x);
			  /*if(a[n]<=x)g<<n<<'\n';
               else if(a[y]!=x)g<<y<<'\n'; 
		        else g<<y<<'\n';} */
             if(a[n]<=x)g<<n<<'\n';  
			   else if(a[y]>x)g<<y-1<<'\n';
		          else g<<y<<'\n';}
			
		  else if(h==2) {y=binary_search(x);
			 /*if(a[y]!=x)g<<y+1<<'\n';
		      else if(a[n]<=x) g<<n<<'\n';
		       else g<<y<<'\n';}*/
			 if(a[1]==x)g<<y<<'\n';
              //else if(a[2]>x) g<<y<<'\n';		  
			   if(a[y]<x)g<<y+1<<'\n';
		         else g<<y<<'\n';}

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