#include<fstream>
using namespace std;
long long int v[100001];
long long int cautbin0(long long int x,long long int c,long long int v[],long long int n){
    long long int s=0;
    for(long long int i=c;i>0;i/=2){
        if(v[s+i]<=x && s+i<=n){
            s+=i;
        }
    }
    if(v[s]==x){
        return s;
    }else{
        return -1;
    }
}
long long int cautbin1(long long int x,long long int c,long long int v[],long long int n){
    long long int s=0;
    for(long long int i=c;i>0;i/=2){
        if(v[s+i]<=x && s+i<=n){
            s+=i;
        }
    }
    return s;
}
long long int cautbin2(long long int x,long long int c,long long int v[],long long int n){
    long long int s=n;
    for(long long int i=c;i>=1;i/=2){
        if(v[s-i]>=x && s-i>=1){
            s-=i;
        }
    }
    return s;
}
int main(){
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    long long int n,t,c=1,x,y;
    in>>n;
    while(c*2<=n){
        c*=2;
    }
    for(long long int i=1;i<=n;i++){
        in>>v[i];
    }
    in>>t;
    for(long long int i=1;i<=n;i++){
        in>>y>>x;
        if(y==0){
            out<<cautbin0(x,c,v,n)<<'\n';
        }
        if(y==1){
            out<<cautbin1(x,c,v,n)<<'\n';
        }
        if(y==2){
            out<<cautbin2(x,c,v,n)<<'\n';
        }
    }
}