#include <fstream>
#include <algorithm>
#define MAXN 100010
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{   int N, M, t, x, V[MAXN], y;
    f>>N;
    for (int i = 1; i <= N; ++i) f>>V[i];
    f>>M;
    while(M--)
    {   f>>t>>x;
        if(t==0)
        {   y = upper_bound(V + 1, V + N + 1, x) - (V + 1);
            if (y >= 1 && y <= N && V[y] == x) g<<y<<'\n'; else g<<"-1\n";
        }
        else if (t == 1)
            {   y = upper_bound(V + 1, V + N + 1, x) - (V + 1);
                g<<y<<'\n';
            }
            else if (t == 2)
                {   y = lower_bound(V + 1, V + N + 1, x) - V;
                    g<<y<<'\n';
                }
    }
    g.close(); return 0;
}