#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
int v[100000],n,m,x;
short q;

int cb0(int i,int j,int x) {
    int m=(i+j)/2;
    if (m==i) {
        if (v[m+1]==x)
            return m+1;
        else
            if (v[m]==x)
                return m;
            else
                return -1;
    }
    else {
        if (v[m]<=x)
            cb0(m,j,x);
        else
            cb0(i,m,x);
    }

}

int cb1(int i,int j,int x) {
    int m=(i+j)/2;
    if (m==i) {
        if (v[m+1]<=x)
            return m+1;
        else
            return m;
    }
    else {
        if (v[m]<=x)
            cb1(m,j,x);
        else
            cb1(i,m,x);
    }

}

int cb2(int i,int j,int x) {
    int m=(i+j)/2;
    if (m==i) {
        if (v[m]>=x)
            return m;
        else
            return m+1;
    }
    else {
        if (v[m]>=x)
            cb2(i,m,x);
        else
            cb2(m,j,x);
    }

}


int main()
{
    fi>>n;
    for (int i=1;i<=n;i++)
        fi>>v[i];
    fi>>m;
    for (int i=1;i<=m;i++) {
        fi>>q>>x;
        if (q==0)
            fo<<cb0(1,n,x)<<'\n';
        else
            if (q==1)
                fo<<cb1(1,n,x)<<'\n';
            else
                fo<<cb2(1,n,x)<<'\n';
    }
    return 0;
}