#include <fstream>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

const int N = 1e5;
int n, x[N + 1], m;

int caut_bin0(int val)
{
    int st = 1, dr = n;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(x[m] <= val)
        {
            st = m + 1;
        }
        else
        {
            //if(x[m] == val)
            //{
            //    while(x[m] == val)
            //        m++;
            //    rez = m - 1;
            //}
            dr = m - 1;
        }
    }
    if(x[dr] == val)
        return dr;
    return -1;
}

int caut_bin1(int val)
{
    int st = 1, dr = n;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(x[m] <= val)
        {
            st = m + 1;
        }
        else
        {
            //if(x[m] == val)
            //{
            //    while(x[m] == val)
            //        m++;
            //    rez = m - 1;
            //}
            dr = m - 1;
        }
    }
    return dr;
}

int caut_bin2(int val)
{
    int st = 1, dr = n;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(x[m] >= val)
        {
            dr = m - 1;
        }
        else
        {
            //if(x[m] == val)
            //{
            //    while(x[m] == val)
            //        m++;
            //    rez = m - 1;
            //}
            st = m + 1;
        }
    }
    return st;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> x[i];
    cin >> m;
    int a, b;
    for(int i = 1; i <= m; i++)
    {
        cin >> a >> b;
        if(a == 0)
            cout << caut_bin0(b) << '\n';
        else
            if(a == 1)
                cout << caut_bin1(b) << '\n';
        else
            cout << caut_bin2(b) << '\n';
    }
    return 0;
}