#include <fstream>
using namespace std;

int v[100001];

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int bsearch0(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+1;
    else
        return -1;
}

int bsearch1(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;
    }

    while(v[m]>x)
        m--;
    return m+1;
}

int bsearch2(int st, int dr, int x)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]>=x)
            dr=m-1;
        else
            st=m+1;
    }

    m=(st+dr)/2;

    while(v[m]<x)
        m++;

    return m+1;
}

int main()
{
    int nr, nrQ;
    fin>>nr;
    for(int i=0; i<nr; i++)
        fin>>v[i];
    fin>>nrQ;

    for(int i=1; i<=nrQ; i++)
    {
        int q, caut;
        fin>>q>>caut;
        if(q==0)
            fout<<bsearch0(0, nr, caut)<<endl;
        else if(q==1)
            fout<<bsearch1(0, nr, caut)<<endl;
        else
            fout<<bsearch2(0, nr, caut)<<endl;
    }

    return 0;

}