#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;
    }

    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;
}