#include<fstream>
#define InFile  "cautbin.in"
#define OutFile "cautbin.out"
#define MAX 100001

using namespace std;

ifstream fin  (InFile);
ofstream fout (OutFile);

unsigned int binsrc1 (unsigned int val);
unsigned int binsrc2 (unsigned int val);

unsigned int N, M;
unsigned int x[MAX];

unsigned int i, a, b, pos;

int main ()
{
    fin >> N;
    for (i=1; i<=N; i++)
        fin >> x[i];
    fin >> M;
    for (i=1; i<=M; i++)
    {
        fin >> a >> b;
        pos = binsrc1(b);
        if (a == 0)
            if (x[pos] == b)
                fout << pos << '\n';
            else
                fout << -1 << '\n';
        else if (a == 1)
                fout << pos << '\n';
        else
                fout << binsrc2(b) << '\n';
    }
    return 0;
}

unsigned int binsrc1 (unsigned int val)
{
    unsigned int left, right, med;
    int last=-1;
    left = 1;
    right = N;
    while (left <= right)
    {
        med = (left+right)/2;
        if (val >= x[med])
        {
            last = med;
            left = med+1;
        }
        else
            right = med-1;
    }
    return last;
}

unsigned int binsrc2 (unsigned int val)
{

    unsigned int left, right, med;
    int last=-1;
    left = 1;
    right = N;
    while (left <= right)
    {
        med = (left+right)/2;
        if (val <= x[med])
        {
            last = med;
            right = med-1;
        }
        else
            left = med+1;
    }
    return last;
}