//#include<stdio.h>
#include<fstream>
#define dim 100000
using namespace std;

int a[dim],x,n;

int cautare_binara0(int x)
    {int l=0, h=n-1, mij;
	 while(a[l]<x && a[h]>=x)
     {mij=l+((x-a[l])*(h-l))/(a[h]-a[l]);
	  if(a[mij]<x)
		  l=mij+1;
	   else if (a[mij]>x) 
		   h=mij-1;
	    else return mij;
	  }
	  if(a[1]==x) return 1;
	  else if(a[n]==x) return n;
	   else if(a[n]<x) return -1;
	  if (a[l]==x)return l;
	    else return -1;
	}
int cautare_binara1(int x)
    {int l=0, h=n-1, mij;
	 while(a[l]<x && a[h]>=x)
     {mij=l+((x-a[l])*(h-l))/(a[h]-a[l]);
	  if(a[mij]<x)
		  l=mij+1;
	   else if (a[mij]>x) 
		   h=mij-1;
	    else return mij;
	  }
	 if(a[n]<=x) return n;
	 if(a[1]==x) return 1;  
	  if (a[mij]>x)return mij-1;
	    else return mij;
	}
int cautare_binara2(int x)
    {int l=0, h=n-1, mij;
	 while(a[l]<x && a[h]>=x)
     {mij=l+((x-a[l])*(h-l))/(a[h]-a[l]);
	  if(a[mij]<x)
		  l=mij+1;
	   else if (a[mij]>x) 
		   h=mij-1;
	    else return mij;
	  }
	 if(a[n]<=x) return n;
	 if(a[1]==x)return 1;
	  if (a[mij]<x)return mij+1;
	    else return mij;
	}
	
	int main()
    {int h,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) g<<cautare_binara0(x)<<'\n';
		    else if(h==1) g<<cautare_binara1(x)<<'\n';
		      else if(h==2) g<<cautare_binara2(x)<<'\n';
		  }
	  f.close();
      g.close();		
	  return 0;
	}