#include <bits/stdc++.h>
using namespace std;

int caut_bin(const vector<int> &v, const int x){
    int sure = 0;
    for(int step = (1<<19)/*2^20*/; step > 0; step /= 2)
        {
            const int candidate = sure+step;
            if(candidate < v.size() && v[candidate] <= x) sure = candidate , cout<<sure<<'\n' ;
        }
    return sure; }

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int n;
    f >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        f >> v[i]; }
    int m;
    f >> m;
    for(int i = 0, t, x; i < m; ++i){
        f >> t >> x;
        if(t == 1)
            g << caut_bin(v, x)+1 << '\n';
        else if(t == 2)
            g << caut_bin(v, x-1)+1 +1 << '\n';
        else{
            const int tmp = caut_bin(v, x);
            if(v[tmp] == x) g << tmp+1 << '\n';
            else g << -1 << '\n'; } }
    return 0; }