#include <iostream>
#include <fstream>

using namespace std;

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

int V[100001];

int Binar0 (int dr, int st, int x)
{
    int mij;

    while (dr <= st)
    {
        mij = (dr + st) / 2;
        if (V[mij] <= x)
            dr = mij + 1;
        else
            st = mij - 1;
    }
    mij = (dr + st) / 2;

    if (V[mij] > x)
        mij --;
    if (V[mij] == x)
        return mij;
    return -1;
}

int Binar1 (int dr, int st, int x)
{
    int mij;

    while (dr < st)
    {
        mij = (dr + st) / 2;
        if (V[mij] <= x)
            dr = mij + 1;
        else
            st = mij;
    }

    mij = (dr + st) / 2;
    if (V[mij] > x)
        mij--;
    return mij;
}

int Binar2 (int dr, int st, int x)
{
    int mij;

    while (dr < st)
    {
        mij = (dr + st) / 2;
        if (V[mij] < x)
            dr = mij + 1;
        else
            st = mij;
    }

    mij = (dr + st) / 2;
    if (V[mij] < x)
        mij++;
    return mij;
}

int main ()
{
    int i, n, m, type, x;
    in>>n;
      for (i = 1; i <= n; i++)
          in>>V[i];

          in>>m;
          while (m--)
        {
            in>>type>>x;

            if (type == 0)
                out<<Binar0(1, n, x)<<'\n';
            if (type == 1)
                out<<Binar1(1, n, x)<<'\n';
            if (type == 2)
                out<<Binar2(1, n, x)<<'\n';
        }
    return 0;
}