#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

const int MAX_SIZE = 100000;
int v[MAX_SIZE + 1], n, m, tip_of_question, number_searched;

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

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

int binary_search2(int number_searched) {
    int left = 1, right = n, middle;
    while (left < right) {
        middle = (left + right) / 2;
        if (v[middle] < number_searched) {
            left = middle + 1; 
        } else {
            right = middle;
        }
    }    
    middle = (right + left) / 2;
    if (v[middle] < number_searched) {
        return middle + 1;
    }
    return middle;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    fin >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> tip_of_question >> number_searched;
        if (tip_of_question == 0) {
            fout << binary_search0(number_searched) << '\n';
        } else if (tip_of_question == 1) {
            fout << binary_search1(number_searched) << '\n';
        } else {
            fout << binary_search2(number_searched) << '\n';
        }
    }
}