#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int NMAX=100001;
int a[NMAX];

int Cautbin0(int li, int ls, int x) {
    int m;
    while(li<=ls) {
        m=(li+ls)/2;
        if(x<=a[m])
            li=m+1;
        else
            ls=m-1;
    }
    m=(li+ls)/2;
    if(a[m]>x) m--;
    if(a[m]==x) return m;
    return -1;
}

int Cautbin1(int li, int ls, int x) {
    int m;
    while (li<ls) {
        m=(li+ls)/2;
        if (a[m]<=x)
            li=m+1;
        else
            ls=m;
    }
    m=(li+ls)/2;
    if(a[m]>x)
       --m;
    return m;
}

int Cautbin2(int li, int ls, int x) {
    int m;
    while(li<ls) {
        m=(li+ls)/2;
        if(a[m]<x)
            li=m+1;
        else
            ls=m;
    }
    m=(li+ls)/2;
    if(a[m]<x)
        ++m;
    return m;
}

int main()
{
    int n,m,x,y;
    fin>>n;
    for(int i=1; i<=n; i++) fin>>a[i];
    fin>>m;
    for(int i=1; i<=m; i++) {
        fin>>x>>y;
        if(x==0) fout<<Cautbin0(1,n,y)<<endl;
        else if(x==1) fout<<Cautbin1(1,n,y)<<endl;
        else fout<<Cautbin2(1,n,y)<<endl;
    }
    return 0;
}