#include <cstdio>

#define Nmax 100001

using namespace std;

int N, M, v[Nmax];

int bin_search(int x) {
    // Find largest pos of x
    int largestPos = -1;
    
    int left = 1;
    int right = N;
    
    do {
        int mid = (left + right) / 2;
        
        
        if(x < v[mid]) {
            right = mid - 1;
        } else if(x > v[mid]) {
            left = mid + 1;
        } else {
            largestPos = mid;
            left = mid + 1;
        }
    
    } while(left <= right);
    
    return largestPos;
}

int bin_search_smaller(int x) {
    int largestPos = -1;
    
    int left = 1;
    int right = N;
    
    do {
        int mid = (left + right) / 2;
        
        
        if(x < v[mid]) {
            right = mid - 1;
        } else {
            largestPos = mid;
            left = mid + 1;
        }
    } while(left <= right);
    
    return largestPos;
}

int bin_search_larger(int x) {
    int largestPos = -1;
    
    int left = 1;
    int right = N;
    
    do {
        int mid = (left + right) / 2;
        
        if(x <= v[mid]) {
            right = mid - 1;
            largestPos = mid;
        } else {
            left = mid + 1;
        }
    } while(left <= right);
    
    return largestPos;
}



int operate(int opType, int x) {

    switch(opType) {
        // Largest pos of x
        case 0:
            return bin_search(x);
        break;
        
        // Largest number < x
        case 1:
            return bin_search_smaller(x);
        break;
        
        // Lowest number > x
        case 2:
            return bin_search_larger(x);
        break;
    }
    
    return -1;
}

int main() { 

    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    
    // Read number vector
    scanf("%d", &N);
    
    for(int i = 1; i <= N; ++i) {
        scanf("%d", &v[i]);        
    }
    
    // Read operations
    scanf("%d", &M);
    
    for(int i = 1; i <= M; ++i) {
        int opType, x;
        
        // Read operation
        scanf("%d%d", &opType, &x);
        
        // Print result
        printf("%d\n", operate(opType, x));
    }
    
    return 0;
}