#include <fstream>
#define nrmax 100002
using namespace std;

int n,V[nrmax];

int f1(int x){
    int st=1,dr=n,mij;
    while(st<=dr){
        mij=(st+dr)/2;
    if(V[mij]<=x)st=mij+1;
    else dr=mij-1;
    }
    mij=(st+dr)/2;
    if(V[mij]>x)--mij;
    if(V[mij]==x)return mij;
    return -1;
}

int f2(int x){
    int st=1,dr=n,mij;
    while(st<dr){
            mij=(st+dr)/2;
    if(V[mij]<=x)st=mij+1;
    else dr=mij;
    }
    mij=(st+dr)/2;
    if(V[mij]>x)--mij;
    return mij;
}

int f3(int x){
    int st=1,dr=n,mij;
    while(st<dr){
            mij=(st+dr)/2;
    if(V[mij]<x)st=mij+1;
    else dr=mij;
    }
    mij=(st+dr)/2;
    if(V[mij]<x)++mij;
    return mij;
}

int main(){
    int q,x,m;
    ifstream input("cautbin.in");
    ofstream print("cautbin.out");
    input>>n;
    for(int i=1;i<=n;++i)input>>V[i];
    input>>q;
    for(int i=1;i<=q;++i){
            input>>m>>x;
    switch(m){
        case 0: print<<f1(x)<<"\n";
                break;
        case 1: print<<f2(x)<<"\n";
                break;
        case 2: print<<f3(x)<<"\n";
                break;
      }
   }
    return 0;
}