#include <bits/stdc++.h>
using namespace std;

int a[100009], n;
///cauta cea mai din dreapta poz unde se alfta x
///sau ret. -1 daca x nu apare in vector
int CB0(int x)
{
    if (x > a[n]) return -1;
    if (x < a[1]) return -1;
    int st, dr, mij, poz;
    st = 1;
    dr = n;
    poz = -1; /// poz cea mai din dr unde este x
    while(st <= dr)
    {
        mij = (st + dr)/2;
        if(a[mij] == x)
        {
            poz = mij;
            ///caut si mai in dr
            st = mij+1;
        }
        else if(a[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }
    return poz;
}
///ret. cea mai din dr pozitie poz cu a[poz] <= x;
int CB1(int x)
{
    if (x < a[1]) return 1;
    if (x >= a[n]) return n;
    int st, dr, mij, poz;
    st = 1;
    dr = n;
    poz = -1;
    while(st <= dr)
    {
        mij = (st + dr)/2;
        if(a[mij] <= x)
        {
            poz = mij;
            st= mij + 1;
        }
        else dr = mij -1;
    }
    return poz;
}
///ret cea mai din stanga poz poz cu x<= a[poz]
int CB2(int x)
{
    if (x <= a[1]) return 1;
    int st, dr, mij, poz;
    st = 1;
    dr = n;
    poz = -1;
    while(st <= dr)
    {
        mij = (st + dr)/2;
        if(x <= a[mij])
        {
            poz = mij;
            dr= mij - 1;
        }
        else st = mij + 1;
    }
    return poz;
}
int main()
{
    int i, M, op, x;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> a[i];
    fin >> M;
    for ( i = 1; i <= M; i++)
    {
        fin >> op >> x;
        if(op == 0) fout << CB0(x) << "\n";
        else if(op == 1) fout << CB1(x) << "\n";
        else fout << CB2(x) << "\n";
    }
    fout.close();

    return 0;
}