#include <fstream>

using namespace std;

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

#define N 100003

int v[N], n, T, tip, x, logN;

int cb0(int key)
{
    int i = 0;
    for(int lg = logN; lg; lg>>=1)
        if(i+lg<=n && v[i+lg]<=key)
            i += lg;

    return v[i]==key ? i:-1;
}

int cb1(int key)
{
    int i = 0;
    for(int lg = logN; lg; lg>>=1)
        if(i+lg<=n && v[i+lg]<=key)
            i += lg;

    return i;
}

int cb2(int key)
{
    int i = n;
    for(int lg = logN; lg; lg>>=1)
        if(i-lg>0 && v[i-lg]>=key)
            i -= lg;

    return i;
}

void citire()
{
    in >> n;

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

    in >> T;

    for(logN = 1; logN < n; logN <<=1 );

    while(T--)
    {
        in >> tip >> x;

        switch(tip)
        {
            case 0 : {out << cb0(x) << "\n";break;}
            case 1 : {out << cb1(x) << "\n";break;}
            case 2 : {out << cb2(x) << "\n";break;}
        }
    }
}

int main()
{
    citire();

    in.close();
    out.close();
    return 0;
}