/* Se citește de la tastatură un vector V sortat crescator de lungime N și apoi un șir de perechi (x, y) 
de numere naturale terminat cu -1. Pe măsura citirii acestor numere, 
să se determine eficient numărul de elemente din V cuprinse între x și y (x < y). Folosiți o căutare binară modificată. */


#include <stdio.h>

int binary_search(int v[], int low, int high, int element, int m) {
    int mid = low + (high - low) / 2;

        if (element >= v[mid]) {
            if (element == v[high]) {
                return high;
            }
            return binary_search(v, mid, high, element, m);
        }
        else {
            if (element < v[mid]) {
                if (element == v[low]) {
                    return low;
                }
                return binary_search(v, low, mid, element, m);
            }    
        }
        if (element == v[mid]) {
            return mid;     
        }
        if (element > v[high] || element < v[low]) {
            switch (m)
            {
            case 0:
                return -1;
                break;
            
            case 1:
                return high;
                break;
            case 2:
                return low;
                break;
            }
        }
}

#define SIZE 100

int main() {
    int v[SIZE], n, m, y, no_questions;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    scanf("%d", &no_questions);
    for (int i = 0; i < no_questions; i++) {
        scanf("%d", &m);
        scanf("%d", &y);
        printf("%d\n", binary_search(v, 0, n, y, m));
        fflush(stdout);
    }
    
    return 0;
}