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

/**
Cautare binara
- Cautarea binara se face doar in valori ordonate
  crescator sau descrescator

- CB micsoreaza timpul de executie

              p dr
a = 2 4 4 7 7 7 10 20 20 30 50 70 77 90
                m
x=46

- Cati pasi face SB?
  R: p pasi, unde p este maxim cu prop. ca 2^p<=n
  n=1000: cel mult 10 pasi
  n=10^6:          20

- La fiecare pas comparam pe x cu a[m], unde m
  este mijlocul intervalului [st,dr], adica
  m = (st + dr) / 2
- Daca a[m] < x, vom cauta la dreapta lui m,
  adica st=m+1
- Daca a[m] > x, vom cauta la stanga lui m,
  adica dr=m-1

Trei tipuri de cautare binara:
1. Cauta in vectorul a ordonat o pozitie unde se afla
   valoare x, sau -1 daca x nu este in a
2. Cauta cea mai din stanga pozitie p cu a[p]>x
2. Cauta cea mai din dreapta pozitie p cu a[p]<x
*/

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[100003], n, m;

/// ret. cea mai din dreapta pozitie p cu a[p]=x
/// ret. -1 daca x nu este in a
int CB0(int x)
{
    if (x < a[1]) return -1;
    if (x > a[n]) return -1;
    int st, dr, mij, p;
    st = 1; dr = n; p = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (a[mij] == x)
        {
            p = mij;
            st = mij + 1;
        }
        else if (a[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }
    return p;
}

/// ret. cea mai din dreapta pozitie p cu a[p]<=x
int CB1(int x)
{
    int st, dr, mij, p;
    st = 1; dr = n; p = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (a[mij] <= x)
        {
            p = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return p;
}

/// ret. cea mai din stanga pozitie p cu a[p]>=x
int CB2(int x)
{
    int st, dr, mij, p;
    st = 1; dr = n; p = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (a[mij] >= x)
        {
            p = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    return p;
}

int main()
{
    int i, op, x;
    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";
        if (op == 1) fout << CB1(x) << "\n";
        if (op == 2) fout << CB2(x) << "\n";
    }
    return 0;
}