#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001];

int cautare1(int s, int d, int val)
{
    int m;

    while(s <= d)
    {
        m = (s + d) / 2;
        if(v[m] <= val)
        {
            s = m + 1;
        }
        else
        {
            d = m - 1;
        }
    }
    m = (s + d) / 2;

    if(v[m] > val) m--;
    if(v[m] == val) return m;

    return -1;
}

int cautare2(int s, int d, int val)
{
    int m;

    while(s < d)
    {
        m = (s + d) / 2;
        if(v[m] <= val)
            s = m + 1;
        else
            d = m - 1 ;
    }

    m = (s + d) / 2;
    if(v[m] > val)
        m--;
    return m;
}

int cautare3(int s, int d, int val)
{
    int m;

    while(s < d)
    {
        m = (s + d) / 2;
        if(v[m] < val)
            s = m + 1;
        else
            d = m - 1;
    }
    m = (s + d) /2;
    if(v[m] < val) m++;
    return m;
}
int main()
{
    int n, m, k, val;
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    while(m)
    {
        fin >> k >> val;
        if(k == 0) fout << cautare1(1, n, val);
        if(k == 1) fout << cautare2(1, n, val);
        if(k == 2) fout << cautare3(1, n, val);
        m--;
    }
    return 0;
}