#include <fstream>
#define fisier "X"
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
int V[100000];
#include <algorithm>
int main()
{
    int n, m;
    in >> n;
    for (int i = 0; i < n; i++)
        in >> V[i];
    in >> m;
    while (m--)
    {
        int o, v;
        in >> o >> v;
        switch (o)
        {
            case 0:
                out << (std::binary_search(V, V+n, v)? std::upper_bound(V, V+n, v) - V: -1) << '\n'; break;
            case 1:
                out << std::upper_bound(V, V+n, v) - V                                        << '\n'; break;
            case 2:
                out << std::lower_bound(V, V+n, v) - V + 1                                    << '\n';
        }
    }
}