#include <fstream>

using namespace std;

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

int v[100001] /* crescator */, n, m;

int leftright1(int mj)
{
    while (1)
    {
        if (v[mj + 1] > v[mj] || mj == n)
        {
            return mj;
        }
        else mj++;
    }
}

int leftright2(int mj, int x)
{
    while (1)
    {
        if (v[mj + 1] > x || mj == n)
        {
            return mj;
        }
        else mj++;
    }
}

int leftright3(int mj, int x)
{
    while (1)
    {
        if (v[mj - 1] < x || mj == 1)
        {
            return mj;
        }
        else mj--;
    }
}

int search1(int x)
{
    int st = 1, dr = n;
    while (st < dr)
    {
        int mj = (st + dr) / 2;
        if (v[mj] == x)
        {
            return leftright1(mj);
        }
        if (v[mj] <= x) st = mj + 1;
        else dr = mj - 1;
    }
    return -1;
}

int search2(int x)
{
    int st = 1, dr = n;
    while (st < dr)
    {
        int mj = (st + dr) / 2;
        if (v[mj] <= x) 
        {
            return leftright2(mj, x);
        }
        else dr = mj - 1;
    }
    return 1;
}

int search3(int x)
{
    int st = 1, dr = n;
    while (st < dr)
    {
        int mj = (st + dr) / 2;
        if (v[mj] >= x) 
        {
            return leftright3(mj, x);
        }
        else st = mj + 1;
    }
    return n;
}

int main()
{
    cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        cin >> v[i];
    }
    cin >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        int tip, x;
        cin >> tip >> x;
        if (tip == 0) cout << search1(x) << endl;
        if (tip == 1) cout << search2(x) << endl;
        if (tip == 2) cout << search3(x) << endl; 
    }
}