#include <iostream>
#include <fstream>
using namespace std;

int p;
int cautbin0 (int a [], int lo, int hi, int x)
{
    int mid;
    if (lo == hi)
    {
        if (a [lo] == x) return lo;
        else return  -1;
    }

    mid = hi - (hi - lo) / 2;

    if (a [mid] > x) return cautbin0 (a, lo, mid - 1, x);
    else return cautbin0 (a, mid, hi, x);
}

int cautbin1 (int a [], int lo, int hi, int x)
{
    int mid;
    if (lo == hi - 1)
    {
        if ((a [lo] == x && a [hi] != x) || a [hi] > x) return lo;
        return hi;
    }

    mid = hi - (hi - lo) / 2;

    if (a [mid] > x) return cautbin1 (a, lo, mid, x);
    else return cautbin1 (a, mid, hi, x);
}

int cautbin2 (int a [], int lo, int hi, int x)
{
    int mid;
    if (lo == hi - 1)
    {
        if ((a [hi] == x && a [lo] != x) || a [lo] < x) return hi;
        else return lo;
    }

    mid = hi - (hi - lo) / 2;

   // cout << "lo = " << lo << "  hi = " << hi << endl;
    if (a [mid] >= x) return cautbin2 (a, lo, mid, x);
    else{
        //cout << "CACAT";
        return cautbin2 (a, mid + 1, hi, x);}
}


int a [100005];

int main()
{
    ifstream f ("cautbin.in");
    ofstream g ("cautbin.out");

    int n, i, q, m, x;

    f >> n;
    for (i = 1; i <= n; ++ i)
        f >> a [i];
    f >> q;
    for (i = 1; i <= q; ++ i)
    {
      //  cout << i << endl;
        f >> m >> x;
        if (m == 0) g << cautbin0 (a, 1, n, x) << '\n';
        if (m == 1) g << cautbin1 (a, 1, n, x) << '\n';
        if (m == 2) g << cautbin2 (a, 1, n, x) << '\n';
    }
    return 0;
}