#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int v[100005];

int cb_gr(int val);
int cb_les(int val);

int main(){

    fin >> n;

    for(int i = 0; i < n; i++){
        fin >> v[i];
    }

    fin >> m;

    for(int i = 0, type, num, pozcb; i < m; i++){
        fin >> type >> num;



        if(type == 0){
            pozcb = cb_gr(num);

            if(v[pozcb-1] == num){
                fout << pozcb << '\n';
            }else{
                fout << "-1\n";
            }

        }else if(type == 1){
            pozcb = cb_gr(num);

            fout << pozcb << '\n';
        }else{
            pozcb = cb_les(num);

            fout << pozcb + 2;
        }
    }

    return 0;
}

int cb_gr(int val){
    int st = 0, dr = n-1, mij, poz = n;

    while(st <= dr){
        mij = (st + dr) / 2;

        if(v[mij] <= val){
            st = mij + 1;
        }else{
            dr = mij - 1;
            poz = mij;
        }
    }

    return poz;
}

int cb_les(int val){
    int st = 0, dr = n-1, mij, poz = -1;

    while(st <= dr){
        mij = (st + dr) / 2;

        if(v[mij] >= val){
            dr = mij - 1;
        }else{
            st = mij + 1;
            poz = mij;
        }
    }

    return poz;
}