#include<iostream>
#include<fstream>
using namespace std; 
long int n, x[100001], val1, m, res,i, cond1;
ifstream f1("cautbin.in");
ofstream f2("cautbin.out");
 
void read()
{
    f1>>n;
    for(i=1; i<=n; i++)
        f1>>x[i];
}
 
long int caut_bin0(long int val)
{
long int st=1, dr=n, poz=-1, mij;
while(st<=dr)
    {
    mij=(dr+st)/2;
    if(x[mij]==val)
    {poz=mij;st=mij+1;}
    if(val<x[mij])
        dr=mij-1;
    else
        st=mij+1;
    }
return poz;
}
 
long int caut_bin2(long int val)
{
long int st=1, dr=n, poz=0, mij;
while(st<dr)
    {
    mij=(dr+st)/2;
    if(x[mij]>=val)
    {dr=mij-1;poz=mij;}
    if(x[mij]<val)
        st=mij+1;
    }
    return poz;
}
 
long int caut_bin1(long int val)
{
long int st=1, dr=n, poz=0, mij;
while(st<dr)
    {
    mij=(st+dr)/2;
    if(x[mij]<=val)
    {st=mij+1;poz=mij;}
    if(x[mij]>val)
        dr=mij-1;
    }
    return poz;
}
 
void solve()
 
{
f1>>m;
 
    while(m)
        {
        f1>>cond1>>val1;
        if(cond1==0)
            f2<<caut_bin0(val1)<<endl;
        if(cond1==1)
            f2<<caut_bin1(val1)<<endl;
        if(cond1==2)
            f2<<caut_bin2(val1)<<endl;
        m--;
        }
}
 
int main(){
    read();
    solve();
return 0;
}