#include<stdio.h>
FILE*f=fopen("cautbin.in","r");
FILE*g=fopen("cautbin.out","w");
int a[100067];
int n,m;
int bs0(int i, int j, int x)
 {
 int m=i+(j-i)/2;
 if(j<i) return -1;
 if(a[m]==x && a[m+1]!=x) return m;
 if(a[m]<x) return bs0(m+1,j,x);
 return bs0(i,m-1,x);
 }
int bs1(int i, int j, int x) // cel mai mare mai mic sau egal cu x
 {
 int m=i+(j-i)/2;
 //if(j<i) return -1;
 if(a[m]<=x && (a[m+1]>x || m==n)) return m;
 if(a[m]<=x) return bs1(m+1,j,x);
 return bs1(i,m-1,x);
 }
int bs2(int i, int j, int x)   //cel mai mic mai mare sau egal cu x
 {
 int m=i+(j-i)/2;
 //if(j<i) return -1;
 if(a[m]>=x && (a[m-1]<x||m-1==0)) return m;
 if(a[m]>=x) return bs2(i,m-1,x);
 return bs2(m+1,j,x);
 }
int main()
 {
 fscanf(f,"%d",&n);
 int i,j;
 for(i=1;i<=n;++i) fscanf(f,"%d",&a[i]);
 fscanf(f,"%d",&m);
 while(m--)
  {
  fscanf(f,"%d %d",&i,&j);
  if(i==0) fprintf(g,"%d\n",bs0(1,n,j));
  else if(i==1) fprintf(g,"%d\n",bs1(1,n,j));
  else fprintf(g,"%d\n",bs2(1,n,j));
  }
 return 0;
 }