#include <fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream f2("cautbin.out");

int n, m, a[100005], optiune, x, i;

int catare0(int lb, int ub, int x){
    int sol = -1;
    while(lb <= ub){
        int mid = (lb + ub) / 2;
        if(a[mid] == x){
            lb = mid + 1;
            sol = mid;
            continue;
        }
        if(a[mid] < x){
            lb = mid + 1;
        }
        else{
            ub = mid - 1;
        }
    }
    return sol;
}

int catare1(int lb, int ub, int x){
    int sol = -1;
    while(lb <= ub){
        int mid = (lb + ub) / 2;
        if(a[mid] <= x){
            lb = mid + 1;
            sol = mid;
        }
        else{
            ub = mid - 1;
        }
    }
    return sol;
}

int catare2(int lb, int ub, int x){
    int sol = -1;
    while(lb <= ub){
        int mid = (lb + ub) / 2;
        if(a[mid] >= x){
            ub = mid - 1;
            sol = mid;
        }
        else{
            lb = mid + 1;
        }
    }
    return sol;
}

int main()
{
    f >> n;
    for(i = 1; i <= n; i++){
        f >> a[i];
    }
    f >> m;
    while(m--){
        f >> optiune >> x;
        if(optiune == 0){
            f2 << catare0(1, n, x) << endl;
        }
        else if(optiune == 1){
            f2 << catare1(1 , n, x) << endl;
        }
        else{
            f2 << catare2(1, n, x) << endl;
        }
    }
    return 0;
}