#include <fstream>
#include <iostream>
#define FILE cautbin
#define N 100005

using namespace std;

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

int n, v[N];

int bsearch0(int st, int dr, int val)
{
    int m, poz = 0;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(v[m] == val)
        {
            poz = m;
            st = m + 1;
        }
        else if(v[m] < val) st = m + 1;
        else if(v[m] > val) dr = m - 1;
    }
    if(poz) return poz;
    return -1;
}

int bsearch1(int st, int dr, int val)
{
    int m, poz = 0;
    while(st <= dr)
    {
        m = (st + dr)/2;
        if(v[m] <= val)
        {
            poz = m;
            st = m + 1;
        }
        else if(v[m] < val) st = m + 1;
        else if(v[m] > val) dr = m - 1;
    }
    if(poz) return poz;
    return -1;
}

int bsearch2(int st, int dr, int val)
{
    int m, poz = 0;
    while(st <= dr)
    {
        m = (st + dr)/2;
        if(v[m] >= val)
        {
            poz = m;
            dr = m - 1;
        }
        else if(v[m] < val) st = m + 1;
        else if(v[m] > val) dr = m - 1;
    }
    if(poz) return poz;
    return -1;
}

int main()
{
    int q, ask, x;
    f >> n;
    for(int i = 1; i <= n; ++i) f >> v[i];
    f >> q;
    while( q-- )
    {
        f >> ask >> x;
        if(ask == 0) g << bsearch0(1, n, x) << '\n';
        else if(ask == 1) g << bsearch1(1, n, x) << '\n';
        else g << bsearch2(1, n, x) << '\n';
    }
    return 0;
}