#include <fstream>
#include <string.h>

using namespace std;

ifstream cin ("cautbin.in");
ofstream cout("cautbin.out");

int bsearch1(int nr, int v[], int dp){
    int mid, st = 0, ret = -2;
    while (st <= dp){
        mid = (st + dp) / 2;
        if (v[mid] == nr){
            ret = mid;
            st = mid + 1;
        }
        else if (v[mid] < nr){
            st = mid + 1;
        }
        else
            dp = mid - 1;
    }
    if (v[st] == nr)
        ret = st;

    return ret + 1;
}

int bsearch2 (int nr, int v[], int dp){
    int mid, st = 0, ret = -1;
    while (st <= dp){
        mid = (dp + st) / 2;
        if (v[mid] <= nr){
            ret = mid;
            st = mid + 1;
        }
        else if (v[mid] > nr)
            dp = mid - 1;
        else
            st = mid + 1;
    }

    if (v[st] <= nr)
        ret = st;

    return ret + 1;
}

int bsearch3 (int nr, int v[], int dp){
    int mid, st = 0, ret = -1;
    while (st <= dp){
        mid = (dp + st) / 2;
        if (v[mid] >= nr){
            ret = mid;
            dp = mid - 1;
        }
        else if (v[mid] > nr)
            dp = mid - 1;
        else
            st = mid + 1;
    }
    if (v[st] >= nr)
        ret = st;

    return ret + 1;
}

int main(){
	int n, v[100000];
	cin >> n;

	for (int i = 0; i < n; ++i)
        cin >> v[i];

    int m, cer, nr;
    cin >> m;
    for (int index = 0; index < m; ++index){
        cin >> cer >> nr;
        if (cer == 0)
            cout << bsearch1(nr, v, n - 1) << "\n";
        else if (cer == 1)
            cout << bsearch2(nr, v, n - 1) << "\n";
        else
            cout << bsearch3(nr, v, n - 1) << "\n";
    }

	return 0;
}