#include <iostream>

using namespace std;

const int NMAX = 1e5 + 10;

int v[NMAX];

int query_1(int x, int n){
    int left, right;
    left = 1;
    right = n;
    int result = -1;
    while(left <= right){
        int middle = (left + right) / 2;
        if(v[middle] == x){
            result = middle;
            left = middle + 1;
        }
        else if(v[middle] > x) right = middle - 1;
        else left = middle + 1;
    }
    return result;
}
int query_2(int x, int n){
    int left, right;
    left = 1;
    right = n;
    int result = -1;

    while (left <= right){
        int middle = (left + right) / 2;
        if(v[middle] <= x){
            result = middle;
            left = middle + 1;
        }
        else if(v[middle] > x) right = middle - 1;
        else left = middle + 1;
    }
    return result;
}

int query_3(int x, int n){
    int left, right;
    left = 1;
    right = n;
    int result = -1;
    while(left <= right){
        int middle = (left + right) / 2;
        if(v[middle] >= x){
            result = middle;
            right = middle - 1;
        }
        else if(v[middle] < x) left = middle + 1;
        else right = middle - 1;

    }
    return result;
}
int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &v[i]);
    }
    int queries;
    scanf("%d", &queries);
    for(; queries > 0; queries--){
        int operation, x;
        scanf("%d %d", &operation, &x);
        if(operation == 0)
            printf("%d\n", query_1(x, n));
        else if(operation == 1)
            printf("%d\n", query_2(x, n));
        else
            printf("%d\n", query_3(x, n));
    }
    return 0;
}