#include <fstream>

using namespace std;

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

int n,m,i,j,t,val;
 long long a[100001],x,st,dr,ml,u;

int main () {
    f >> n;
    for (i=1;i<=n;i++) f >> a[i];
    f >> m;
    for (i=1;i<=m;i++) {
        f >> t >> x;
        val=-1;
        if (t==0) {
            st=1;dr=n;
            while (st<=dr) {
                ml=(st+dr)/2;
                if (a[ml]<=x) st=ml+1;
                if (a[ml]>x) dr=ml-1;
            }
            u=(st+dr)/2;if (a[u]>x) u--; if (a[u]!=x) u=-1;
            val=u;
        }
        if (t==1) {
            st=1;dr=n;
            while (st<dr) {
                ml=(st+dr)/2;
                if (a[ml]<=x) st=ml+1;
                if (a[ml]>x) dr=ml;
            }
            u=(st+dr)/2;if (a[u]>x) u--;val=u;
        }
        if (t==2) {
            st=1;dr=n;
            while (st<dr) {
                ml=(st+dr)/2;
                if (a[ml]<x) st=ml+1;
                if (a[ml]>=x) dr=ml;
            }
            u=(st+dr)/2;if (a[u]<x) u++;val=u;
        }
        g << val << '\n';
    }
    f.close();g.close();
    return 0;
}