/*
Se da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul:
0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
*/

#include <fstream>

using namespace std;

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

int v[100001];

int caz0(int st,int dr,int x) {

    int mij;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (v[mij]<=x)//conditia (1)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    mij = (st + dr) / 2;
    if (v[mij]>x)//exista posibiliatatea ca v[mij] sa fie mai mare ca x din conditia (1)
        mij--;
    if (x == v[mij]) return mij;

    return -1;
}

int caz1(int st,int dr,int x) {
    int mij;
    while (st < dr) {
        mij = (st + dr) / 2;
        if ( v[mij]<=x)
            st = mij + 1;
        else
            dr = mij;
    }
    mij = (st + dr) / 2;
    if (x < v[mij])//din garantare / ramane o obtiune ca sa fie mai mare si mai scadem un index
        mij--;
    return mij;
}

int caz2(int st,int dr,int x) {
    int mij;
    while (st < dr) {
        mij = (st + dr) / 2;
        if (v[mij]<x)
            st = mij + 1;
        else
            dr = mij;
    }

    mij = (st + dr) / 2;
    if (v[mij]<x)//din garantare/ ramane o obtiune ca sa fie mai mic si mai crestem un index
        mij++;
    return mij;
}

int main() {

    int n, m, nr_caz, x;
    f>> n;
   for (int i = 1; i <= n;i++)
        f>>v[i];
    f>> m;
    while(m)  {
        f>> nr_caz >> x;
        if(nr_caz == 0)
            g << caz0(1,n,x)<<"\n";
        if(nr_caz == 1)
            g << caz1(1,n,x) <<"\n";
        if(nr_caz == 2)
            g << caz2(1,n,x) <<"\n";
        m--;
    }

    f.close();
    g.close();

    return 0;
}