#include<fstream>
 
using namespace std;
 
ifstream f ("cautbin.in");
ofstream g("cautbin.out");
int n,i,t,x,v[100005],m;
 
int cautbinar0(int st, int dr, int x)
{
    int m;
    while (st<=dr)
    {
        m=(st+dr)/2;
        if (v[m]<=x) st=m+1;
        else dr=m-1;
    }
    m=(st+dr)/2;
    if (v[m]>x) m--;
    if (v[m]==x) return m;
    return -1;
}
 
int cautbinar1(int st, int dr, int x)
{
    int m;
    while (st<dr)
    {
        m=(st+dr)/2;
        if (v[m]<=x) st=m+1;
        else    dr=m;
    }
    m=(st+dr)/2;
    if (v[m]>x)  --m;
    return m;
}
 
int cautbinar2(int st, int dr, int x)
{
    int m;
    while (st<dr)
    {
        m=(st+dr)/2;
        if (v[m]<x)  st=m+1;
        else    dr=m;
    }
    m=(st+dr)/2;
    if (v[m]<x)  ++m;
    return m;
}
 
int main ()
{
    f>>n;
    for (i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>t>>x;
        if (t==0)   g<<cautbinar0(1,n,x)<<"\n";
        if (t==1)   g<<cautbinar1(1,n,x)<<"\n";
        if (t==2)   g<<cautbinar2(1,n,x)<<"\n";
    }
    f.close();
    g.close();
    return 0;
}