#include<iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N,a[100005], M;

int solve1(int x)
{
    int poz = -1;

    int st = 1;
    int dr = N;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (a[mij] == x && mij > poz)
        {
            poz = mij;
            st = mij + 1;
        }
        if (x > a[mij])
        {
            st = mij + 1;
        }
        if (x < a[mij])
        {
            dr = mij - 1;
        }
    }
    return poz;
}
int solve2(int x)
{
    int poz = -1;

    int st = 1;
    int dr = N;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (a[mij] <= x && mij > poz)
        {
            poz = mij;
            st = mij + 1;
        }
        if (x > a[mij])
        {
            st = mij + 1;
        }
        if (x < a[mij])
        {
            dr = mij - 1;
        }
    }
    return poz;
}
int solve3(int x)
{
    int poz = N;

    int st = 1;
    int dr = N;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (a[mij] >= x && mij < poz)
        {
            poz = mij;
            dr = mij - 1;
        }
        if (a[mij] < x)
        {
            st = mij + 1;
        }
        if (a[mij] >= x)
        {
            dr = mij - 1;
        }
    }
    return poz;
}
int main()
{
    f>>N;
    for(int i=1; i<=N; i++)
    {
        f>>a[i];
    }
    f>>M;
    for(int i=0; i<M; i++)
    {
        int op, x;
        f>>op >> x;

        if (op == 0)
        {
            g<<solve1(x) << '\n';
        }
        if (op == 1)
        {
            g << solve2(x) << '\n';
        }
        if (op == 2)
        {
            g << solve3(x) << '\n';
        }
    }

}