#include <iostream>
#include <fstream>
using namespace std;

#define FILE_NAME "cautbin"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");

constexpr unsigned MAX_DIM = 100000 + 16;
unsigned Elements[MAX_DIM];
unsigned N, M;

unsigned binarySearch_highest(unsigned X)
{
    unsigned Result = 1;

    unsigned step = 1<<30;
    while(step)
    {
        if(Result + step <= N && Elements[Result + step] <= X)
            Result += step;
        step >>= 1;
    }

    return Result;
}

unsigned binarySearch_lowest(unsigned X)
{
    unsigned Result = N;

    unsigned step = 1<<30;
    while(step)
    {
        if(Result > step && Elements[Result - step] >= X)
            Result -= step;
        step >>= 1;
    }

    return Result;
}

int main()
{
    in >> N;
    for(unsigned i = 1; i <= N; ++i)
        in >> Elements[i];

    in >> M;
    while(M--)
    {
        unsigned code, x;
        in >> code >> x;

        switch(code)
        {
        case 0:
            {
                unsigned poz = binarySearch_highest(x);
                if(Elements[poz] == x)
                    out << poz << '\n';
                else
                    out << "-1\n";
                break;
            }
        case 1:
            {
                out << binarySearch_highest(x) << '\n';
                break;
            }
        case 2:
            {
                out << binarySearch_lowest(x);
                break;
            }
        default:
            {
                cerr << "Code unrecognized!";
                return -1;
            }
        }
    }

    return 0;
}