#include <iostream>
#include <fstream>

#define nmax 100001
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int N,M;
int A[nmax];

inline int oper0(long x)
{
    int hi=N , lo = 0;
        while (hi - lo > 1)
        {
           long mi;
           mi = (hi+lo) / 2;
            if (A[mi] <= x) lo = mi;
                else hi = mi - 1;
        }
        if (A[hi] == x) return hi;
            else
            {
                if (A[lo] == x) return lo;
                    else return (-1);
            }
}

inline int oper1(long x)
{
  int hi=N , lo = 0;
        while (hi - lo > 1)
        {
           long mi;
           mi = (hi+lo) / 2;
            if (A[mi] <= x) lo = mi;
                else hi = mi - 1;
        }
        if (A[hi] == x) return hi;
            else
                return lo;
}

inline int oper2(long x)
{
     int hi=N , lo = 0;
        while (hi - lo > 1)
        {
           long mi;
           mi = (hi+lo) / 2;
            if (A[mi] >= x ) hi = mi;
                else lo = mi ;
            /*if (A[mi] < x) lo = mi;
                else hi = mi - 1;*/
        }
        if (A[hi] == x)
        {
            if (A[lo] == x) return lo;
                else  return hi;
        }
        else return hi;
}

int main()
{
    f >> N;
    for (int i= 1; i <= N; i++)
        f >> A[i];
    f >> M;
     for (int i = 0; i < M; i++ )
     {
         int op; long x;
         f >> op >> x;
         if (op == 0) { /* op = 0 */ g << oper0(x) << '\n'; }
            else {
                if (op == 1) { /* op = 1 */ g << oper1(x) << '\n'; }
                    else{
                        /* op = 2 */
                        g << oper2(x) << '\n';
                    }
            }
    }


    return 0;
}