using namespace std;
#include <fstream>
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, nr;
int v[100010];

int cautbin0() ;
int cautbin1() ;
int cautbin2() ;

int main()
{
    int i, m, tip;
    fin>>n;
    for(i=1; i<=n; ++i) fin>>v[i];
    v[0]=-1; v[n+1]=v[n]+5;

    fin>>m;
    for(i=0; i<m; ++i)
    {
        fin>>tip>>nr;
        if(tip==0) fout<<cautbin0()<<'\n';
        else if(tip==1) fout<<cautbin1()<<'\n';
        else fout<<cautbin2()<<'\n';
    }
    return 0;
}


int cautbin0()
{
    int st=1, dr=n, mijl;
    while(st<=dr)
    {
        mijl=(st+dr)/2;
        if(v[mijl]<=nr) st=mijl+1;
        else dr=mijl-1;
    }
    if(v[mijl]>nr) --mijl;
    if(v[mijl]==nr) return mijl;
    return -1;
}

int cautbin1()
{
    int st=1, dr=n, mijl;
    while(st<dr)
    {
        mijl=(st+dr)/2;
        if(v[mijl]<=nr) st=mijl+1;
        else dr=mijl;
    }
    mijl=(st+dr)/2;
    if(v[mijl]>nr) --mijl;
    return mijl;
}


int cautbin2()
{
    int st=1, dr=n, mijl;
    while(st<dr)
    {
        mijl=(st+dr)/2;
        if(v[mijl]<nr) st=mijl+1;
        else dr=mijl;
    }
    mijl=(st+dr)/2;
    if(v[mijl]<nr) ++mijl;
    return mijl;
}