#include<iostream>
#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n, i, j, x, y, m;
int v[100002];

int cbin0(int s, int d) {

    int poz=-1;

    while (s <= d) {

        int m= (s+d) / 2;
        if (v[m] == x) {
            poz=m;
            s=m+1;
        } else if (v[m] < x) {
            s=m+1;
        } else {
            d=m-1;
        }
    }

    return poz;
}

int cbin1(int s, int d) {

    int poz=0;

    while(s<=d){
        int m=(s+d)/2;

        if (v[m]<=x) {
            poz=m;
            s=m+1;
        } else {
            d=m-1;
        }
    }

    return poz;
}

int cbin2(int s, int d) {

    int poz=0;

    while (s <= d) {
        int m= (s+d ) / 2;

        if (v[m] >= x) {
            poz=m;
            d=m-1;
        } else {
            s=m+1;
        }
    }

    return poz;
}

int main() {

    f>>n;
    for (i=1; i<=n; i++) f>>v[i];
    f>>m;

    for (i=1; i<=m; i++){
        f>>y>>x;
        if (y == 0) {
            g << cbin0 (1, n) << '\n';
        } else if (y ==1) {
            g << cbin1 (1, n) << '\n';
        } else if (y == 2) {
            g << cbin2 (1, n) << '\n';
        }
    }

}