/* 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>
#include <stdlib.h>

int binary_search(int v[], int low, int high, int element, int m) {
    int mid = low + (high - low) / 2;
    //printf("%d low , %d high %d mid\n", low, high, mid);
    if (v[mid] == element) {
            return mid + 1;
        }  
    else {
        if (high <= low || low > high) {
            if (m == 0) {
                return -1;
            }
            if (m == 1) {
                if (high == low) {
                    return mid + 1;
                }
                else
                {
                    return low;
                }
                
            }
            if (m == 2) {
                return high + 1;
            }
            
        }
        if (v[mid] <= element) {
            low = mid + 1;
            return binary_search(v, low, high, element, m);
        }   
        if (v[mid] > element) {
            high = mid - 1;
            return binary_search(v, low, high, element, m);
        }
    }      
}
    

#define SIZE 100

int main() {
    	
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    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("searching for %d mode %d\n", y, m);
        printf("%d\n",binary_search(v, 0, n - 1, y, m));
        fflush(stdout);
    }
    return 0;
}