#include <fstream>
using namespace std;
int v[100005], n, s, d, m, ma;

int f0(int a)
{
    s=1;
    d=n;
    while(s<d){
        ma=m;
        m=(s+d)/2;
        if(ma==m)
            break;
        if(v[m]<=a)
            s=m;
        else
            d=m-1;}
    while(v[d]>a)
        d--;
    if(v[d]==a)
        return d;
    return -1;
}

int f1(int a)
{
    s=1;
    d=n;
    while(s<d){
        ma=m;
        m=(s+d)/2;
        if(ma==m)
            break;
        if(v[m]<=a)
            s=m;
        else
            d=m-1;}
    while(v[d]>a)
        d--;
    return d;

}

int f2(int a)
{
    s=1;
    d=n;
    while(s<d){
        m=(s+d)/2;
        if(v[m]<a)
            s=m+1;
        else
            d=m;}
    if(v[s]<a)
        s++;
    return s;
}

int main()
{
    ifstream in ("cautbin.in");
    ofstream out ("cautbin.out");
    int i, m, f, e;
    in>>n;
    for(i=1;i<=n;++i)
        in>>v[i];
    in>>m;
    for(i=1;i<=m;++i){
        in>>f>>e;
        switch(f){
        case 0:
            out<<f0(e)<<'\n';
            break;
        case 1:
            out<<f1(e)<<'\n';
            break;
        case 2:
            out<<f2(e)<<'\n';
            break;
        default:
            break;}}
    return 0;
}