#include <fstream>
#include <vector>

std::vector<int> v;

int quickSearch1(int);
int quickSearch2(int);
int quickSearch3(int);

int main()
{
    std::ifstream fin ("cautbin.in");
    std::ofstream fout ("cautbin.out");
    int n, x, t;
    fin >> n;
    while(n--){
        fin >> x;
        v.push_back(x);
    }
    fin >> n;
    while(n--){
        fin >> t >> x;
        if (t == 0)
            fout << quickSearch1(x) << "\n";
        else if (t == 1)
            fout << quickSearch2(x) << "\n";
        else fout << quickSearch3(x) << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}

int quickSearch1(int x){
    int lo = 0, hi = v.size()-1, m;
    if (v[hi] == x)
        return hi+1;
    for (m = lo + ((hi-lo) >> 1); lo <= hi; m = lo + ((hi-lo) >> 1))
        if(v[m] == x && v[m+1] > x)
            return m+1;
        else if (v[m] <= x)
            lo = m + 1;
        else hi = m - 1;
    return -1;
}

int quickSearch2(int x){
    int lo = 0, hi = v.size()-1, m;
    if (v[hi] <= x)
        return hi+1;
    for (m = lo + ((hi-lo) >> 1); lo <= hi; m = lo + ((hi-lo) >> 1))
        if(v[m] <= x && v[m+1] > x)
            return m+1;
        else if (v[m] <= x)
            lo = m + 1;
        else hi = m - 1;
    return -1;
}

int quickSearch3(int x){
    int lo = 0, hi = v.size()-1, m;
    if (v[lo] >= x)
        return lo+1;
    for (m = lo + ((hi-lo) >> 1); lo <= hi; m = lo + ((hi-lo) >> 1))
        if(v[m] >= x && v[m-1] < x)
            return m+1;
        else if (v[m] >= x)
            hi = m - 1;
        else lo = m + 1;
    return -1;
}