#include<fstream>
#define inf "cautbin.in"
#define outf "cautbin.out"
#define NMax 100001
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int N,M;
int v[NMax];

int caut0(int nr)
{
int st,dr,mij,p;
bool gasit=false;
st=1;
dr=N;
while(st<=dr)
    {
    mij=(st+dr)/2;
    if(v[mij]==nr)
        {
        gasit=true;
        p=mij;
        st=mij+1;
        }
    else if(v[mij]<nr)st=mij+1;
    else dr=mij-1;
    }
if(gasit)return p;
return -1;
}

int caut1(int nr)
{
int st,dr,mij,p;
st=1;
dr=N;
while(st<=dr)
    {
    mij=(st+dr)/2;
    if(v[mij]<=nr)
        {
        p=mij;
        st=mij+1;
        }
    else dr=mij-1;
    }
return p;
}

int caut2(int nr)
{
int st,dr,mij,p;
st=1;
dr=N;
while(st<=dr)
    {
    mij=(st+dr)/2;
    if(v[mij]>=nr)
        {
        p=mij;
        dr=mij-1;
        }
    else st=mij+1;
    }
return p;
}

void Citire()
{
int q,nr;
f>>N;
for(int i=1;i<=N;i++)f>>v[i];
f>>M;
for(int i=1;i<=M;i++)
    {
    f>>q>>nr;
    if(q==0)g<<caut0(nr)<<"\n";
    else if(q==1)g<<caut1(nr)<<"\n";
    else g<<caut2(nr)<<"\n";
    }
}

int main()
{
Citire();
f.close();
g.close();
return 0;
}