#include <fstream>

using namespace std;

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

int BinSrc1 (unsigned int val);
int BinSrc2 (unsigned int val);

unsigned int N;
unsigned int A[100001];
unsigned int M;
unsigned int type, x;

unsigned int pos;
unsigned int i;

int main ()
{
    fin >> N;
    for (i=1; i<=N; i++)
        fin >> A[i];
    fin >> M;
    for (i=1; i<=M; i++)
    {
        fin >> type >> x;
        pos = BinSrc1(x);
        if (type == 0)
            if (A[pos] == x)
                fout << pos << '\n';
            else
                fout << -1 << '\n';
        else
            if (type == 1)
                fout << pos << '\n';
            else
                fout << BinSrc2(x) << '\n';
    }
    return 0;
}

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

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