//#include <iostream>
//#include <fstream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>

/* cea mai mare pozitie pe care se afla un element cu valoarea x
 sau -1 daca aceasta valoare nu se gaseste in sir */
int first_question(std::vector<int> &vector, int left, int right, int element) {
    int pivot;
    
    while (left <= right) {
        pivot = left + (right - left) / 2;
        
        if (element >= vector[pivot])
            left = pivot + 1;
        else
            right = pivot - 1;
    }
    
    pivot = left + (right - left) / 2;
    
    if (vector[pivot] > element)
        pivot--;
    if (vector[pivot] == element)
        return pivot;
    
    return -1;
}

/* cea mai mare pozitie pe care se afla un element cu valoarea mai mica
 sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului
 este mai mic sau egal decat x */
int second_question(std::vector<int> &vector, int left, int right, int element) {
    int pivot;
    
    while (left < right) {
        pivot = left + (right - left) / 2;
        
        if (element >= vector[pivot])
            left = pivot + 1;
        else
            right = pivot;
    }
    
    pivot = left + (right - left) / 2;
    
    if (vector[pivot] > element)
        --pivot;
    
    return pivot;
}
/* cea mai mica pozitie pe care se afla un element cu valoarea
mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare
numar din sir este mai mare sau egal decat x */
int third_question(std::vector<int> &vector, int left, int right, int element) {
    int pivot;
    
    while (left < right) {
        pivot = left + (right - left) / 2;
        
        if (element <= vector[pivot])
            right = pivot;
        else
            left = pivot + 1;
    }
    
    pivot = left + (right - left) / 2;
    
    if (vector[pivot] < element)
        ++pivot;
    
    return pivot;
}


int main () {
    int i, n, m, tip, val;
    
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    std::vector<int> vector(n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &vector[i]);
    
    scanf("%d", &m);
    
    while (m--){
        scanf("%d%d", &tip, &val);
        if (tip == 0)
            printf("%d\n", first_question(vector, 0, n - 1, val));
        if (tip == 1)
            printf("%d\n", second_question(vector, 0, n - 1, val));
        if (tip == 2)
            printf("%d\n", third_question(vector, 0, n -1, val));
    }
    
    exit(0);
}