#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)/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)/2;
if(j<i) return -1;
if(a[m]<=x && a[m+1]>x) 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)/2;
if(j<i) return -1;
if(a[m]>=x && a[m-1]<x) 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;
}