#include <iostream>
#include <fstream>

using namespace std;

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

void citire(int & n, int x[])
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>x[i];
}

int cautBin_0(int n, int x[], int cautat)
{
    int stanga = 1, dreapta = n;
    while(stanga < dreapta)
    {
        int mijloc = (stanga+dreapta+1)/2;
        if(x[mijloc]>cautat)
            dreapta = mijloc-1;
        else
            stanga = mijloc;
    }
    if(x[stanga] == cautat)
        return stanga;
    else
        return -1;
}

int cautBin_1(int n, int x[], int cautat)
{
    int stanga = 1, dreapta = n;
    while(stanga < dreapta)
    {
        int mijloc = (stanga+dreapta+1)/2;
        if(x[mijloc]>cautat)
            dreapta = mijloc-1;
        else
            stanga = mijloc;
    }
    return stanga;
}

int cautBin_2(int n, int x[], int cautat)
{
    int stanga = 1, dreapta = n;
    while(stanga < dreapta)
    {
        int mijloc = (stanga+dreapta)/2;
        if(x[mijloc]>=cautat)
            dreapta = mijloc;
        else
            stanga = mijloc+1;
    }
    return dreapta;
}

int main()
{
    int n, x[100001], m;

    citire(n, x);
    fin >> m;
    for(int i = 1; i <= m; i++)
    {
        int p, nr;
        fin >> p >> nr;
        if(p == 0)
            fout << cautBin_0(n, x, nr) << '\n';
        else if(p == 1)
            fout << cautBin_1(n, x, nr) << '\n';
        else
            fout << cautBin_2(n, x, nr) << '\n';
    }


    return 0;
}