#include <iostream>
#include <fstream>

using namespace std;

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

int v[100005], n, i, t, cer, x, p;

int cautbin1(int st, int dr, int elem)
{
    p = -1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij] == elem)
        {
            p = mij;
            st = mij + 1;
        }
        else if(v[mij] < elem) st = mij  + 1;
        else dr = mij - 1;
    }
    return p;
}

int cautbin2(int st, int dr, int elem)
{
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij] <= elem) st = mij + 1;
        else dr = mij - 1;
    }
    return dr;
}

int cautbin3(int st, int dr, int elem)
{
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[mij] >= elem) dr = mij - 1;
        else st = mij + 1;
    }
    return st;
}

int main()
{
    f >> n;

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

    f >> t;
    while(t --)
    {
        f >> cer >> x;
        if(cer == 0) g << cautbin1(1, n, x) << "\n";
        else if(cer == 1) g << cautbin2(1, n, x) << "\n";
        else g << cautbin3(1, n, x) << "\n";
    }
    return 0;
}