#include <fstream>

using namespace std;

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

int a[100005],n,k,i,j,q,x,st,dr,m;

int main() {
    f >> n;
    for (i = 1; i <= n; i++)
        f>>a[i];
    for(f>>k;k--;) {
        f >> q>>x;
        st=1,dr=n;
        if (q==0) {
            while(st<=dr) {
                m = (st+dr)/2;
                if (a[m]>x)
                    dr=m-1;
                else st=m+1;
            }
            g << (a[dr]!=x?-1:dr) << '\n';
        }
        else if (q==1) {
            while(st<dr) {
                m = (st+dr)/2;
                if (a[m]>x)
                    dr=m-1;
                else st=m+1;
            }
            if(a[dr]>x)
                dr--;
            g << dr << '\n';
        }
        else {
            while(st<dr) {
                m = (st+dr)/2;
                if (a[m]>=x)
                    dr=m-1;
                else st=m+1;
            }
            if(a[dr]<x)
                dr++;
            g << dr << '\n';
        }
    }
    return 0;
}