#include <iostream>
#include <fstream>
#define nmax 100001
using namespace std;

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

int hi,lo,mid;
int n,v[nmax];

void bin0(int x){
    hi=n+1;
    lo=0;
    
    while (hi-lo>1){
        mid=lo+(hi-lo)/2;
        if (v[mid]<=x) lo=mid;
        else hi=mid;
    }
    
    if (v[lo]==x) cout << lo << "\n";
    else out << -1 << "\n";
    
}

void bin1(int x){
    hi=n+1;
    lo=0;
    
    while (hi-lo>1){
        mid=lo+(hi-lo)/2;
        if (v[mid]<=x) lo=mid;
        else hi=mid;
    }
    
    out << lo << "\n";
    
}

void bin2(int x){
    hi=n+1;
    lo=0;
    
    while (hi-lo>1){
        mid=lo+(hi-lo)/2;
        if (v[mid]>=x) hi=mid;
        else lo=mid;
    }
    
    out << hi << "\n";
    
}

int main(){
    
    int i,a,x,t;
    
    in >> n;
    for (i=1; i<=n; i++)
        in >> v[i];
    v[n+1]=v[i]+1;
    
    in >> t;
    for (i=1; i<=t; i++){
        in >> a >> x;
        
        if (!a){
            bin0(x);
        } else if (a==1){
            bin1(x);
        } else {
            bin2(x);
        }
        
    }
    return 0;
}