#include <fstream>

using namespace std;

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

int n, a[100001], m, cer, x;

int cautbin0(int x){
    int p=-1, u=n, mij;
    while(u-p > 1){
        mij = (p+u)/2;
        if(a[mij] <= x)
            p = mij;
        else
            u = mij;
       // fout << p<<' '<<u<<' '<<mij<<' '<<a[mij]<<' '<<'\n';
    }
    if(a[u] > x)
        u--;
    //fout << u<<' ' << a[u]<<'\n';
    if(u==n || a[u]!=x)
        return -1;
    else
        return u+1;
}

int cautbin1(int x){
    int p=-1, u=n, mij;
    while(u-p > 1){
        mij = (p+u)/2;
        if(a[mij] <= x)
            p = mij;
        else
            u = mij;
    }
    if(a[u]>x || u==n)
        u--;
    return u+1;
}


int cautbin2(int x){
    int p=-1, u=n, mij;
    while(u-p > 1){
        mij = (p+u)/2;
        if(a[mij] < x)
            p = mij;
        else
            u = mij;
    }
    //if(a[u] > x)
       // u--;
    return u+1;
}

int main(){
    fin >> n;
    for(int i=0; i<n; i++)
        fin >> a[i];
    fin >> m;
    for(int i=1; i<=m; i++){
        fin >> cer >> x;
        if(cer == 0)
            fout << cautbin0(x) << '\n';
        if(cer == 1)
            fout << cautbin1(x) << '\n';
        if(cer == 2)
            fout << cautbin2(x) << '\n';
    }
    return 0;
}