#include <iostream>
#include <fstream>

using namespace std;

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

int n,m,v[100003];

int bs0(int l, int r, int x){
    int m;
    while(l<r-1){

        m = l + (r-l)/2;

        if(v[m] == x) l = m;
        else  {
            if(v[m] > x) r = m - 1;
            else l = m + 1;
        }

    }

    if(v[l] > x) m--;

    if(v[l] == x) return l;
    else return -1;
}

int bs1(int l, int r, int x){
    int m;
    while(l<r-1){
        m = l + (r-l)/2;
        if(v[m] > x) r = m - 1;
        else l = m;
    }

    if(v[l] > x) l--;

    return l;
}

int bs2(int l, int r, int x){
    int m;

    while(l < r ){

        m = l + (r-l)/2;
        if(v[m] >= x) r = l;
        else l = m + 1;
    }

    return l;


}


int main()
{
    int i,opt,x;
    f>>n;
    for(i=1;i<=n;++i) f>>v[i];

    f>>m;

    for(i=1;i<=m;++i){

        f>>opt>>x;

        if(opt == 0) g<<bs0(1,n,x)<<"\n";

        if(opt == 1) g<<bs1(1,n,x)<<"\n";

       if(opt == 2) g<<bs2(1,n,x)<<"\n";

    }
    return 0;
}