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

long long binary_search(unsigned long x)
      {long 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()
    {long 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((y==1)&&(a[1]!=x))g<<-1<<'\n';
		      else g<<y<<'\n';}
		  else if(h==1) {y=binary_search(x);
			 if(y==1)g<<y<<'\n';
                else g<<y-1<<'\n';}		  
		  else if(h==2) {y=binary_search(x);
			 if(y==1)g<<y<<'\n';
		       else g<<y+1<<'\n';}
		  }
	  f.close();
      g.close();		
	  return 0;
	}