#include <fstream>

using namespace std;

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

#define MAX 100010

int v[MAX];

int caut0(int s, int d, int x)
{
    int m;

    while(s<=d)
    {
        m=(s+d)/2;

        if(v[m]<=x)
            s=m+1;
        else
            d=m-1;
    }

    m=(s+d)/2;

    if(v[m]>x)
        m--;

    if(v[m]==x)
        return m;

    return -1;
}

int caut1(int s, int d, int x)
{
    int m;

    while(s<d)
    {
        m=(s+d)/2;
        if(v[m]<=x)
            s=m+1;
        else
            d=m;
    }

    m=(s+d)/2;

    if(v[m]>x)
        --m;

    return m;
}

int caut2(int s, int d, int x)
{
    int m;

    while(s<d)
    {
        m=(s+d)/2;
        if(v[m]<x)
            s=m+1;
        else
            d=m;
    }

    m=(s+d)/2;

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

    return m;
}
int main()
{
    int N,M,i,val,tip;

    fin>>N;

    for(i=1;i<=N;i++)
        fin>>v[i];

    fin>>M;

    while(M)
    {
        fin>>tip>>val;

        if(tip==0)
            fout<<caut0(1,N,val)<<'\n';
        if(tip==1)
            fout<<caut1(1,N,val)<<'\n';
        if(tip==2)
            fout<<caut2(1,N,val)<<'\n';

        M--;
    }

    return 0;
}