#include <bits/stdc++.h>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

int n, nr[1000001], m, tI, x, i, j, poz;

int main()
{
    in >> n;
    for(i = 1; i <= n; i++)
        in >> nr[i];

    in >> m;
    for(i = 1; i <= m; i++)
    {
        in >> tI >> x;
        poz = 0;

        if(tI == 0)
        {
            for(j = 1 << 20; j > 0; j/=2)
            {
                if(poz + j <= n
                   && nr[poz + j] <= x)
                    poz += j;
            }
            if(nr[poz] == x)
                    out << poz << '\n';
                else
                    out << -1 << '\n';
        }

        if(tI == 1)
        {
            for(j = 1 << 20; j > 0; j/=2)
            {
                if(poz + j <= n
                   && nr[poz + j] <= x)
                    poz += j;
            }
            if(nr[poz] <= x)
                    out << poz << '\n';
        }

        if(tI == 2)
        {
            for(j = 1 << 20; j > 0; j/=2)
            {
                if(poz + j <= n
                   && nr[poz + j] <= x)
                    poz += j;
            }
            if(nr[poz] < x)
                    out << poz + 1 << '\n';
            else
                while(nr[poz] == nr[poz - 1])
                    poz--;
                out << poz << '\n';
        }
    }

    return 0;
}