#include <iostream>
#include <fstream>

using namespace std;

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

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

int cb0(int x, int n){
    int st = 1, dr=n, rez=-1;
    int mij;
    while (st<=dr){
        mij = (st+dr)/2;
        if (v[mij]==x) st = mij+1, rez = mij;
        else if (v[mij] < x) st = mij+1;
        else dr = mij-1;
    }
    return rez;
}
int cb1(int x, int n){
    int st = 1, dr=n;
    int mij, poz=0;
    while (st<=dr){
        mij = (st+dr)/2;
        if (v[mij]<=x) st = mij+1, poz=mij;
        else dr = mij-1;
    }
    return poz;
}
int cb2(int x, int n){
    int st = 1, dr=n;
    int mij, poz=0;
    while (st<=dr){
        mij = (st+dr)/2;
        if (v[mij]>=x) dr = mij-1, poz=mij;
        else st = mij+1;
    }
    return poz;
}

int main() {
    fin >> n;
    for (int i=1; i<=n; i++){
        fin >> v[i];
    }
    fin >> m;
    for (int i=1; i<=m; i++){
        fin >> c >> x;
        if (c==0){
            int r = cb0(x, n);
            fout << r << '\n';
        }
        else if (c==1){
            int r = cb1(x, n);
            fout << r << '\n';
        }
        else if (c==2){
            int r = cb2(x, n);
            fout << r << '\n';
        }
    }
    return 0;
}