#include <fstream>
using namespace std;

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

int n, a[100002];

int rez0(int x)
{
    int st = 1;
    int dr = n;
    int m;
    int z = -1;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(a[m] == x)
        {
            if(m > z)
            {
                z = m;
            }
        }
        if(a[m] <= x)
        {
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    return z;
}

int rez1(int x)
{
    int st = 1;
    int dr = n;
    int m;
    int z = -1;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(a[m] <= x)
        {
            if(m > z)
            {
                z = m;
            }
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    return z;
}

int rez2(int x)
{
    int st = 1;
    int dr = n;
    int m;
    int z = n + 1;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(a[m] >= x)
        {
            if(m < z)
            {
                z = m;
            }
            dr = m - 1;
        }
        else
        {
            st = m + 1;
        }
    }
    return z;
}

int main()
{
    int m, x, y;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    cin >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> y >> x;
        if (y == 0)
        {
            int z = rez0(x);
            cout << z << '\n';
        }
        else
            if(y == 1)
            {
                int z = rez1(x);
                cout << z << '\n';
            }
            else
            {
                int z = rez2(x);
                cout << z << '\n';
            }
    }
}