#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
bool comp(int a, int b)
{
    return a <= b;
}
int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int N, M;
    in >> N;
    vector<int> elements(N);
    for(int i = 0; i < N; ++i)
        in >> elements[i];
    sort(elements.begin(), elements.end());
    in >> M;
    for(int i = 0, type, query; i < M; ++i)
    {
        in >> type >> query;
        int exact;
        switch(type)
        {
            case 0:
                exact = upper_bound(elements.begin(), elements.end(), query) - elements.begin() - 1;
                if(elements[exact] == query)
                    out << exact + 1 << "\n";
                else
                    out << -1 << "\n";
                break;
            case 1:
                out << lower_bound(elements.begin(), elements.end(), query, comp) - elements.begin() - 1 + 1<< "\n";
                break;
            case 2:
                exact = upper_bound(elements.begin(), elements.end(), query) - elements.begin();
                out << (elements[exact - 1] == query ? exact - 1 : exact) + 1 << "\n";
                break;
        }
    }
    in.close();
    out.close();
    return 0;
}