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


    return 0;
}