#include <bits/stdc++.h>

using namespace std;

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

int n, v[1000001], m, ins, x, i, j, poz;

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

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

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

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

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

    return 0;
}