#include <bits/stdc++.h>

#define MaxN 100005

std::ifstream InFile("cautbin.in");
std::ofstream OutFile("cautbin.out");

int N, Q, V[MaxN];

int main()
{
    InFile >> N;
    for (int i=0; i<N; ++i)
        InFile >> V[i];

    InFile >> Q;

    int Type, x, p;
    while (Q--) {
        InFile >> Type >> x;

        if (Type == 0) {
            p = std::upper_bound(V, V+N, x) - V - 1;
            if (p && V[p] != x) p = -1;
        } else
        if (Type == 1) {
            p = std::upper_bound(V, V+N, x) - V;
        } else
        if (Type == 2) {
            p = std::lower_bound(V, V+N, x) - V + 1;
        }

        OutFile << p << '\n';
    }

  return 0;
}