// Cautare binara infoarena

#include <iostream>
#include <fstream>
using namespace std;

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

int main() {
    int n, m, v[100001], i, x, nr, poz;
    bool gasit;
    fin >> n;
    for(i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    for(i = 1; i <= m; ++i) {
        fin >> nr >> x;
        int st, dr, mid;
        st = 1;
        dr = n;
        gasit = false;
        if(nr == 0) {
            while(st < dr) {
                mid = (st + dr) / 2; // mid = lo + (hi-lo)/2
                if(v[mid] == x && (mid == n || v[mid + 1] > x && !gasit)) {
                    poz = mid;
                    gasit = true;
                } else if(v[mid] > x) {
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }
            fout << poz << '\n';
        } else if(nr == 1) {
            while(st < dr) {
                mid = (st + dr) / 2;
                if(v[mid] <= x && (mid == n || v[mid + 1] > x && !gasit)) {
                    poz = mid;
                    gasit = true;
                } else if(v[mid] > x) {
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }
            fout << poz << '\n';
        } else if(nr == 2) {
            while(st < dr) {
                mid = (st + dr) / 2;
                if(v[mid] >= x && (mid == n || v[mid + 1] > x && !gasit)) {
                    poz = mid;
                    gasit = true;
                } else if(v[mid] > x) {
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }
            fout << poz << '\n';
        }
    }
    return 0;
}
/*
 1 3 3 3 5


 */