#include <iostream>
#include <fstream>

using namespace std;

int v[100010];

int cautare1(int a, int b, int x)
{
    int m;
    while(a <= b)
    {
        m = (a + b) / 2;
        if(v[m] <= x)
            a = m+1;
        else
            b = m-1;
    }
    m = (a + b) / 2;
    if(v[m] > x)
        m--;
    if(v[m] == x)
        return m;
    return -1;
}

int cautare2(int a, int b, int x){
    int m;

    while(a < b)
    {
        m = (a+b)/2;
        if(v[m] <= x)
            a = m+1;
        else
            b = m;
    }
    m = (a+b)/2;
    if(v[m] > x)
        m--;
    return m;
}

int cautare3(int a, int b, int x)
{
    int m;
    while(a < b)
    {
        m = (a+b)/2;
        if(v[m] < x)
            a = m+1;
        else
            b = m;
    }
    m = (a+b)/2;
    if(v[m] < x)
        m++;
    return m;
}

int main()
{
    int n, m, a, b;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> v[i];
    f >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> a >> b;
        if(a == 0)
            g << cautare1(1, n, b) << ' ';
        if(a == 1)
            g << cautare2(1, n, b) << ' ';
        if(a == 2)
            g << cautare3(1, n, b) << ' ';
    }
    return 0;
}