#include <bits/stdc++.h>

using namespace std;

ofstream g("cautbin.out");

int n, a[100050];

///Cauta cea mai din dr poz == x
void CB0(int x)
{
    int st, dr, m, poz;
    st = 1;
    dr = n;
    poz = -1;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(x == a[m])
        {
            poz = m;
            st = m + 1;
        }
        else if (x < a[m]) dr = m - 1;
        else st = m + 1;
    }
    g << poz << "\n";
}

///ea mai mare pozitie pe care se afla un
///element cu valoarea mai mica sau egala cu x
void CB1(int x)
{
    int st, dr, m, poz;
    st = 1;
    dr = n;
    poz = -1;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(x >= a[m])
        {
            poz = m;
            st = m + 1;
        }
        else dr = m - 1;
    }
    g << poz << "\n";
}

///cea mai mica pozitie pe care se afla un element
///cu valoarea mai mare sau egala cu x in sir
void CB2(int x)
{
    int st, dr, m, poz;
    st = 1;
    dr = n;
    poz = -1;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(x <= a[m])
        {
            poz = m;
            dr = m - 1;
        }
        else st = m + 1;
    }
    g << poz << "\n";
}
void Citire()
{
    int i, k, op, x;
    ifstream f("cautbin.in");
    f >> n;
    for(i = 1; i <= n; i++)
        f >> a[i];
    f >> k;
    for(i = 1; i <= k; i++)
    {
        f >> op >> x;
        if(op == 0) CB0(x);
        else if(op == 1) CB1(x);
        else CB2(x);
    }
    f.close();
}

int main()
{
    Citire();
    g.close();
    return 0;
}