#include<stdio.h>
#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 mij;
	    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[1]>x)return 0; 
	 if(a[n]<=x) return n;
	 else if(a[1]==x)return 1;
	  if (a[mij]<x)return mij+1;
	    else return mij;
	}
	
	int main()
    {int h,m,i;
	FILE*f=fopen ("cautbin.in","r");
	FILE*g=fopen("cautbin.out","w");
	 fscanf(f,"%d",&n); 
	 for(i=1;i<=n;i++)
		 fscanf(f,"%d",&a[i]);
	 fscanf(f,"%d",&m);
	 for(i=1;i<=m;i++)
		 {fscanf(f,"%d%d",&h,&x); 
          if(h==0) fprintf(g,"%d\n",cautare_binara0(x));
		    else if(h==1) fprintf(g,"%d\n",cautare_binara1(x));
		      else if(h==2) fprintf(g,"%d\n",cautare_binara2(x));
		  }
	  fclose(f);
      fclose(g);		
	  return 0;
	}