#include <bits/stdc++.h>
using namespace std;
int v[2000001];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main() {
    int n; 
    fin>>n;
    for (int i = 0; i < n; i++){
        fin>>v[i];
    }
    int t; 
    fin>>t;
    for(int i=1;i<=t;++i) {
        int c, x;
        fin>>c>>x;
        if (c == 2) {
            int* val=lower_bound(v, v + n, x);
            fout << (int)(val - v) + 1 << "\n";
        }
        else if (c == 1) {
            int* val=upper_bound(v, v + n, x);
            fout<< (int)(val - v) << "\n"; // poziția 1-based a lui (p-1)
        }
        else { 
            int* val=upper_bound(v, v + n, x);
            if (val == v) {
                fout<<-1<<"\n";
            } else {
                if (*(val - 1) == x) 
                    fout<< (int)(val - v) <<"\n";
                else fout<<-1<< "\n";
            }
        }
    }
    return 0;
}