#include <iostream>
#include <fstream>

using namespace std;


int pozitieMax(int start, int stop, int value, int values[]);

int binarySearch0(int lo, int hi, int key, int values[]){
    int mid;
    int lastPoz=-1;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (values[mid] == key) {
            lastPoz = mid;
            lo = mid + 1;
        }else if (values[mid] < key) {
            lo = mid+1;
        } else {
            hi = mid-1;
        }
    }
    return lastPoz;
}

int binarySearch1(int lo, int hi, int key, int values[]){
    int mid;
    int lastPoz = -1;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (values[mid] == key) {
            lastPoz = mid;
            lo = mid + 1;
        }else if (values[mid] < key) {
            lo = mid+1;
        } else {
            hi = mid-1;
        }
    }
    mid = (lo + hi) / 2;
    if (lastPoz == -1) {
        if ( values[mid] > key) {
            mid--;
        }
        return mid;
    } else {
        return lastPoz;
    }
}


int binarySearch2(int lo, int hi, int key, int values[]){
    int mid;
    int lastPoz = -1;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (values[mid] == key) {
            lastPoz = mid;
            hi = mid - 1;
        }else if (values[mid] < key) {
            lo = mid+1;
        } else {
            hi = mid-1;
        }
    }
    mid = (lo + hi) / 2;
    if (lastPoz == -1) {
        if ( values[mid] < key) {
            mid++;
        }
        return mid;
    } else {
        return lastPoz;
    }
}


int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    long n, m;
    f>>n;
    int values[n+1];
    for (int i = 1; i <= n; ++i) {
        f>>values[i];
    }
    f>>m;
    for (int i = 0; i < m; ++i) {
        int type, key;
        f>>type>>key;
        if (type == 0) {
            g<<binarySearch0(1, n, key, values);
        } else if (type == 1) {
            g<<binarySearch1(1,n, key, values);
        } else {
            g<<binarySearch2(1, n, key, values);
        }
        g<<'\n';
    }
}