#include <fstream>
#include <cstdio>
#include <cstdlib>
#define MAX_SIZE 100001

int vect[MAX_SIZE];
int N , M;

using namespace std;

int caut_binar(int elem)
{
    int left = 1;
    int right = N;
    while ( left <= right)
    {
        int middle = (left + right) / 2;
        if (vect[middle] == elem) return middle;
        else
        {
            if (vect[middle] < elem) left = middle + 1;
            else right = middle - 1;
        }
    }

    return -1;
}

int cel_mai_mare(int elem)
{
    int left = 1;
    int right = N;
    int middle;
    int poz;
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (vect[middle] <= elem)
        {
            left = middle +1;
            poz = middle;
        }
        else right = middle - 1;
    }
    return poz;
}

int cel_mai_mic(int elem)
{
    int left = 1;
    int right = N;
    int middle;
    int poz;
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (elem <= vect[middle])
        {
            right = middle - 1;
            poz = middle;
        }
        else left = middle + 1;
    }
    return poz;
}

int main()
{
    ifstream input("cautbin.in");
    ofstream output("cautbin.out");
    input >> N;
    for (int i =1;i<=N;i++)
    {
        input >> vect[i];
    }
    input >> M;
    int op , elem;

    for(int i =0;i<M;i++)
    {
        input >> op >> elem;
        if (op == 0)
        {
            if (caut_binar(elem) != -1)
            {
                output << cel_mai_mare(elem) << "\n";
            }
            else
            {
                output << "-1\n";
            }
        }
        if (op == 1)
        {
            output << cel_mai_mare(elem) << "\n";
        }
        if (op == 2)
        {
            output << cel_mai_mic(elem) << "\n";
        }
    }
    input.close();
    output.close();


    return 0;
}