#include <fstream>

using namespace std;

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

const int NM = 100001;
const int L = 16;

int n, v[NM];

int caut0(int x)
{
    int r = 0, pas = 1 << L;
    while(pas!=0)
    {
        if(r+pas <= n&&v[r+pas]<=x)
        {
            r+=pas;
        }
        pas /= 2;
    }
    if(v[r]!=x)
    {
        return -1;
    }
    return r;
}

int caut2(int x)
{
    int r = 0, pas = 1 << L;
    while(pas!=0)
    {
        if(r+pas <= n&&!(v[r+pas]>=x))
        {
            r+=pas;
        }
        pas /= 2;
    }
    r++;
    return r;
}

int caut1(int x)
{
    int r = 0, pas = 1 << L;
    while(pas!=0)
    {
        if(r+pas <= n&&v[r+pas]<=x)
        {
            r+=pas;
        }
        pas /= 2;
    }
    return r;
}

int main()
{
    int nre;
    int x;
    int counter;
    in >> nre;
    int cerinta;
    for(counter = 0; counter < nre; counter++)
    {
        in >> v[counter];
    }
    int nri;
    in >> nri;
    for(counter = 0; counter < nri; counter++)
    {
        in >> cerinta >> x;
        if(cerinta == 0)
        {
            out << caut0(x) << "\n";
        }
        if(cerinta == 1)
        {
            out << caut1(x) << "\n";
        }
        if(cerinta == 2)
        {
            out << caut2(x) << "\n";
        }

    }
    return 0;
}