#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
 
int n, m;
vector<int> v;
 
int lowbound(int val);
int upbound(int val);
 
int main(){
 
    fin >> n;
 
    v.resize(n);
 
    for(int i = 0; i < n; i++){
        fin >> v[i];
    }
 
    fin >> m;
 
    for(int i = 0, c, temp; i < m; i++){
        fin >> c >> temp;
 
        if(c == 0){
            int x = upbound(temp);
 
            if(v[x-1] == temp){
                fout << x << '\n';
            }else{
                fout << "-1\n";
            }
 
        }else if(c == 1){
            fout << upbound(temp) << '\n';
        }else{
            fout << lowbound(temp) + 1 << '\n';
        }
    }
 
    return 0;
}
 
int lowbound(int val){
    int step = 1, poz = 0;
 
    while(step < n){
        step <<= 1;
    }
 
    step >>= 1;
 
    while(step > 0){
        if(step + poz < n && v[step + poz] < val){
            poz += step;
        }
 
        step >>= 1;
    }
    
    if(poz == 0 && v[0] > val){
        return 0;
    }

    return poz+1;
}
 
int upbound(int val){
    int step = (1 << 30), poz = INT_MAX;
 
    while(step > 0){
        if(poz - step >= n || v[poz - step] > val){
            poz -= step;
        }
 
        step >>= 1;
    }

    return poz;
}