#include <iostream>
#include <fstream>

#define MAXN 100000

using namespace std;

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

int v[MAXN], n;

int binsearch0(int x)
{
    int left = 0, right = n - 1, p = -1;

    while(left <= right) {
        int mid = (left + right) / 2;

        if(v[mid] <= x) {
            if(v[mid] == x)
                p = mid;
            left = mid + 1;
        } else
            right = mid - 1;
    }

    if(p >= 0)
        return p + 1;

    return -1;
}


int binsearch1(int x)
{
    int left = 0, right = n - 1, p = 0;

    while(left <= right) {
        int mid = (left + right) / 2;

        if(x >= v[mid])
            p = mid, left = mid + 1;
        else
            right = mid - 1;
    }

    return p + 1;
}

int binsearch2(int x)
{
    int left = 0, right = n - 1, p = 0;

    while(left <= right) {
        int mid = (left + right) / 2;

        if(x <= v[mid])
            p = mid, right = mid - 1;
        else
            left = mid + 1;
    }

    return p + 1;
}


int main(void)
{
    int m, i, c, x;

    fin >> n;

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

    fin >> m;

    while(m--) {
        fin >> c >> x;

        if(c == 0)
            fout << binsearch0(x) << '\n';
        else if(c == 1)
            fout << binsearch1(x) << '\n';
        else
            fout << binsearch2(x) << '\n';
    }

    return 0;
}