#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001],n;
int caz0(int st,int dr,int x) {

    int mij;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (x >= v[mij])
            st = mij + 1;
        else
            dr = mij - 1;
    }
    mij = (st + dr) / 2;
    if (x < v[mij])
        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 (x >= v[mij])
            st = mij + 1;
        else
            dr = mij;
    }
    mij = (st + dr) / 2;
    if (x < v[mij])
        mij--;
    return mij;
}

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

    mij = (st + dr) / 2;
    if (x > v[mij])
        mij++;
    return mij;
}

int main() {

    int  m, nr_caz, x;
    f>> n;
   for (int i = 1; i <= n; ++i)
        f>>v[i];
    f>> m;
    for (int i = 1; i <= m; ++i)  {
        f>> nr_caz >> x;
        if(nr_caz == 0)
            g << caz0(1,n,x)<<endl;
        else if(nr_caz == 1)
            g << caz1(1,n,x) <<endl;
        else
            g << caz2(1,n,x) <<endl;
    }
    f.close();
    g.close();

    return 0;
}