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

const int N=100001;
int v[N],n;

int caut1(int x){
    int i,pos=1<<16;
    for(i=0 ; pos!=0 ; pos>>=1){
            if (i+pos<=n && v[i+pos]<=x){
                    i+=pos;
            }
    }
    return i;
}
int caut0(int x){
    int i=caut1(x);
    if (v[i]!=x)
        return -1;
    return i;
}
int caut2(int x){
    int i,pos=1<<16;
    for (i = 0; pos!=0 ; pos>>=1) {
        if (i+pos<=n && v[i+pos]<x){
            i+=pos;
		}
    }
    return i+1;
}

int main() {
    int m,x,y;
    in>>n;
    for (int i = 1; i <= n; i++) {
        in>>v[i];
    }
    in>>m;
    for (int i = 1; i <= m; i++) {
        in>>y>>x;
        switch (y){
            case 0:{
                out<<caut0(x)<<"\n";
                break;
            }
            case 1:{
                out<<caut1(x)<<"\n";
                break;
            }
            case 2:{
                out<<caut2(x)<<"\n";
                break;
            }
            default:{
                //throw new Exception("eroare in main: switch");       oops am uitat...
                out<<"a intervenit o eroare in main la switch"<<"\n";
                break;
            }
        }
    }

    return 0;
}