#include<stdio.h>
long i,n,a[100100],mij,x,y,z;
long minamin(long l,long r, long s,long y)
{mij=0;
    if(y==0)
{while(l<=r)
{mij=l+(r-l)/2;
if(a[mij]<=s)
l=mij+1;
else
r=mij-1;}
mij=l+(r-l)/2;
if(a[mij]>s)
mij--;
if(a[mij]==s)
return mij;
return -1;}
else
 if(y==1)
{while(l<r)
{mij=l+(r-l)/2;
if(a[mij]<=s)
l=mij+1;
else
r=mij;}
mij=l+(r-l)/2;
if(a[mij]>s)
--mij;
return mij;}
else
 if(y==2)
{while(l<r)
{mij=l+(r-l)/2;
if(a[mij]<s)
l=mij+1;
else
r=mij;}
mij=l+(r-l)/2;
if(a[mij]<s)
++mij;
return mij;}}
int main()
{freopen("cautbin.in", "r", stdin);
freopen("cautbin.out", "w", stdout); 
scanf("%d", &n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);  
 scanf("%d", &x);
for(i=1;i<=x;i++)
{scanf("%d%d", &y, &z);
printf("%d\n",minamin(1,n,z,y));}
fclose(stdin);
fclose(stdout);
return 0;}