#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int i,n,a[100020],x,y=0,z=0;
void citire()
{f>>n;
for(i=1;i<=n;i++)  
{f>>a[i];}
f>>x;} 
int minamin(int l,int r, int s)
{int 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()
{citire();
for(i=0;i<x;i++)
{f>>y>>z;
 g<<minamin(1,n,z)<<endl;}
f.close();
g.close();
return 0;}