#include <fstream>

using namespace std;

#define INFILE "cautbin.in"
#define OUTFILE "cautbin.out"
#define VMAX 100001

ifstream fin (INFILE);
ofstream fout (OUTFILE);

int n, v[VMAX];

int cautBin1(int val){

    int st = 1, dr = n;

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

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

    }

    return -1;

}

int cautBin2(int val){

    int st = 1, dr = n, ans = -1;

    while(st <= dr){

        int mij = (st + dr) / 2;

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

    }

    return ans;

}

int cautBin3(int val){

    int st = 1, dr = n, ans = -1;

    while(st <= dr){

        int mij = (st + dr) / 2;

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

    }

    return ans;

}

void solve(){

    fin >> n;

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

    int q, tip, val;

    fin >> q;

    for(int i = 0; i < q; ++i){

        fin >> tip >> val;

        if(tip == 0){
            fout << cautBin1(val) << '\n';
        }
        else if(tip == 1){
            fout << cautBin2(val) << '\n';
        }
        else{
            fout << cautBin3(val) << '\n';
        }

    }

}

int main(){
    solve();
    return 0;
}