#include <fstream>
#define N 100001
using namespace std;

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

int n, m, a[N];

bool (*cond1)(int,int), (*cond2)(int,int), (*cond3)(int,int), (*cond4)(int,int);
int (*res)(int,int,int);

bool cond_eq(int x, int y) {return x == y;}
bool cond_l(int x, int y) {return x < y;}
bool cond_g(int x, int y) {return x > y;}
bool cond_leq(int x, int y) {return x <= y;}
bool cond_geq(int x, int y) {return x >= y;}
int res_12(int st, int dr, int x) {return cond4(a[dr], x) ? st : -1; }
int res_3(int st, int dr, int x) {return cond4(a[st], x) ? st + 1 : -1; }

int srch(int st, int dr, int x)
{
    if (cond_g(st, dr))
        return res(st, dr, x);
    int m = st+((dr-st)>>1);
    if (cond2(x, a[m]))
        return srch(st, m-1, x);
    else if (cond3(x, a[m]))
        return srch(m+1, dr, x);
}

int main()
{
    int x, y;
    f >> n;
    for (int i = 0; i < n; i++)
        f >> a[i];
    f >> m;
    for (;m;m--)
    {
        f >> x >> y;
        if (x == 0)
        {
            cond2 = cond_l;
            cond3 = cond_geq;
            cond4 = cond_eq;
			res = res_12;
            g << srch(0, n-1, y) << "\n";
        }
        else if (x == 1)
        {
            cond2 = cond_l;
            cond3 = cond_geq;
            cond4 = cond_leq;
			res = res_12;
            g << srch(0, n-1, y) << "\n";
        }
        else
        {
            cond2 = cond_leq;
            cond3 = cond_g;
            cond4 = cond_geq;
			res = res_3;
            g << srch(0, n-1, y) << "\n";
        }
    }
    return 0;
}