#include <fstream>

using namespace std;

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

const int NMAX = 100000 + 5;

int N, Q;
int v[NMAX];

int BS0(int val)
{
    int st = 1, dr = N, mid, sol = -1;

    while(st <= dr)
    {
        mid = (st + dr) >> 1;

        if(v[mid] == val)
        {
            sol = mid;
            st = mid + 1;
        }

        if(v[mid] > val)
            dr = mid - 1;
        else
            st = mid + 1;
    }

    if(sol != -1)
        return sol;

    return -1;
}

int BS1(int val)
{
    int st = 1, dr = N, mid, sol = -1;

    while(st <= dr)
    {
        mid = (st + dr) >> 1;

        if(v[mid] <= val)
        {
            sol = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }

    return sol;
}

int BS2(int val)
{
    int st = 1, dr = N, mid, sol = -1;

    while(st <= dr)
    {
        mid = (st + dr) >> 1;

        if(v[mid] >= val)
        {
            sol = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }

    return sol;
}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> v[i];

    fin >> Q;

    int type, x;
    for(int i = 1; i <= Q; i++)
    {
        fin >> type >> x;

        if(type == 0)
            fout << BS0(x) << '\n';
        else if(type == 1)
            fout << BS1(x) << '\n';
        else
            fout << BS2(x) << '\n';
    }

    return 0;
}