#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100005], st, lf, n, m, q, Q, poz;

int CB(int lf, int rg, int x){
    if(lf>rg){
        return -1;
    }
    int mid=(lf+rg)/2;
    if(v[mid]==x){
        return max(mid, CB(mid+1, rg, x));
    }
    if (v[mid]>x){
        return CB(lf, mid-1, x);
    }
    if (v[mid]<x){
        return CB(mid+1, rg, x);
    }
}
int LB(int lf, int rg, int x){
    if(lf>rg){
        return -2000000000;
    }
    int mid=(lf+rg)/2;
    if(v[mid]>x){
        return LB(lf, mid-1, x);
    }
    else if(v[mid]<=x){
        return max(mid, LB(mid+1, rg, x));
    }
}
int UB(int lf, int rg, int x){
    if(lf>rg){
        return 200000000;
    }
    int mid=(lf+rg)/2;
    if(v[mid]<x){
        return UB(mid+1, rg, x);
    }
    else if(v[mid]>=x){
        return min(mid, UB(lf, mid-1, x));
    }

}
void read()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    fin>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>q>>Q;
        if (q==0){
            fout<< CB(1, n, Q)<<"\n";
        }
        if(q==1){
            fout<<LB(1, n, Q)<<"\n";
        }
        if(q==2){
            fout<<UB(1, n, Q)<<"\n";
        }
    }
}
int main()
{
    read();
    return 0;
}