#include<fstream>
using namespace std;
int i,n,a[100020],mij=0,x,y,z;
int minamin(int l,int r, int s)
{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=0; i<x;i++)
{scanf("%d%d", &y, &z);
printf("%d\n",minamin(1,n-1,z));}
return 0;}