#include <iostream>
#include <fstream>
using namespace std;
int n, m, a[500001], tipCaut, x;

int cautbin0(int s, int d){
if (s > d)
    return -1;
int m = s + (d-s) / 2;
while (a[m] == x){
    m++;}
return m;
if (a[m] < x)
    return cautbin0(m+1, d);
return cautbin0(s, m-1);
}

int cautbin1(int s, int d){
if (s > d)
    return -1;
int m = s + (d-s) / 2;
while (a[m] <= x){
    m++;}
return m;
if (a[m] > x)
    return cautbin1(s,m-1);
}

int cautbin2(int s, int d){
if (s > d)
    return -1;
int m = s + (d-s) / 2;
if (a[m] >= x)
    return m;
if (a[m] < x)
    return cautbin1(m+1, d);
}


int main()
{ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
in >> n;
for (int i = 0 ; i < n ; ++i)
    in >> a[i];
in >> m;
for (int i = 0 ; i < m ; ++i){
    in >> tipCaut >> x;
    if (tipCaut == 0)
        out << cautbin0(0, n-1) << '\n';
    else if (tipCaut == 1)
        out << cautbin1(0,n-1) << '\n';
    else out << cautbin2(0, n-1) << '\n';
}
in.close();
out.close();

}