#include <iostream>
#include <fstream>

using namespace std;

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

int n, m, c, x, v[100003];

int cautaBinar(const int cerinta, const int s, const int d) {
    int m = s + (d-s)/2;
    switch(cerinta) {
        case 0: {
            if(v[m] == x && v[m+1] > x) return m;
            else if(v[m] > x) return cautaBinar(0, s, m-1);
            else return cautaBinar(0, m+1, d);
            break;
        } case 1: {
            if(v[m] <= x && v[m+1] > x) return m;
            else if(v[m] > x) return cautaBinar(1, s, m-1);
            else return cautaBinar(1, m+1, d);
            break;
        } case 2: {
            if(v[m] >= x && v[m-1] < x) return m;
            else if(v[m] < x) return cautaBinar(2, m+1, d);
            else return cautaBinar(2, s, m-1);
            break;
        }
    }
}

int main()
{
    in >> n;
    for(int i = 1; i <= n; i++) {
        in >> v[i];
    }
    in >> m;
    for(int i = 0; i < m; i++) {
        in >> c >> x;
        out << cautaBinar(c, 1, n) << "\n";
    }
    return 0;
}