#include <iostream>
#include <fstream>
#define M 100000
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100000];
int cautbin0(int x, int n){
    int dr = n;
    int st = 1;
    int pos = -1;
    while(st<=dr){
        int m = (st+dr)/2;
        if(x == v[m]) pos = m;
        if(x<v[m])
            dr = m-1;
        else st = m+1;
    }
    return pos;
}
int cautbin1(int x, int n){
    int dr = n;
    int st = 1;
    int pos = 0;
    while(st<=dr){
        int m = (st+dr)/2;
        if(v[m]<=x) {
                pos = m;
                st = m + 1;
        }
        else dr = m-1;
    }
    return pos;
}
int cautbin2(int x, int n){
    int dr = n;
    int st = 1;
    int pos = n;
    while(st<=dr){
        int m = (st+dr)/2;
        if(v[m]>=x) {
                pos = m;
                dr = m - 1;
        }
        else st = m+1;
    }
    return pos;
}
int main(){
    int n;
    in>>n;
    for(int i = 1; i<=n; i++){
        in>>v[i];
    }
    int k, x, a;
    in>>k;
    for(int i = 1; i<=k; i++){
        in>>a>>x;
        if(a==0) out<<cautbin0(x, n)<<endl;
        if(a==1) out<<cautbin1(x, n)<<endl;
        if(a==2) out<<cautbin2(x, n)<<endl;
    }
}