#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1e5 + 7;

int n;

int v[DIM];

int cb0(int x)
{
    int l = 1;
    int r = n;

    int rez = -1;

    while(l <= r)
    {
        int mid = (l + r) / 2;

        if(v[mid] <= x)
        {
            if(v[mid] == x)
                rez = mid;
            l = mid + 1;
        }
        else
        r = mid - 1;
    }
    return rez;
}

int cb1(int x)
{
    int l = 1;
    int r = n;

    int rez = -1;

    while(l <= r)
    {
        int mid = (l + r) / 2;

        if(v[mid] <= x)
        {
            rez = mid;
            l = mid + 1;
        }
        else
        r = mid - 1;
    }
    return rez;
}

int cb2(int x)
{
    int l = 1;
    int r = n;

    int rez = n;

    while(l <= r)
    {
        int mid = (l + r) / 2;

        if(v[mid] >= x)
        {
            rez = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return rez;
}

int main()
{
    in >> n;

    for(int i = 1; i <= n; i++)
        in >> v[i];

    int m;
    in >> m;

    while(m--)
    {
        int q, x;
        in >> q >> x;

        if(q == 0)
            out << cb0(x);
        else
         if(q == 1)
             out << cb1(x);
        else
            out << cb2(x);

        out <<'\n';
    }
    return 0;
}