#include <cstdio>
#define NMAX 100005
using namespace std;
FILE *fin, *fout;
int n, v[NMAX], m;
int main()
{
    int i, t, nr, p, u, m, bun;
    fin=fopen("cautbin.in", "r"); fout=fopen("cautbin.out", "w");
    fscanf (fin, "%d", &n); for (i=1; i<=n; ++i) fscanf (fin, "%d", &v[i]);
    fscanf (fin, "%d", &m);
    for (i=1; i<=m; ++i) {
        fscanf (fin, "%d%d", &t, &nr);
        if (t==0) {
            p=1; u=n; bun=-1;
            while (p<=u) {
                m=p+(u-p)/2;
                if (v[m]==nr) { bun=m; p=m+1; } else
                if (v[m]<nr) p=m+1; else
                if (v[m]>nr) u=m-1;
            }
            fprintf (fout, "%d\n", bun);
        } else
        if (t==1) {
            p=1; u=n; bun=-1;
            while (p<=u) {
                m=p+(u-p)/2;
                if (v[m]<=nr) { bun=m; p=m+1; }
                else u=m-1;
            }
            fprintf (fout, "%d\n", bun);
        }
        else {
            p=1; u=n; bun=-1;
            while (p<=u) {
                m=p+(u-p)/2;
                if (v[m]>=nr) { bun=m; u=m-1; }
                else p=m+1;
            }
            fprintf (fout, "%d\n", bun);
        }
    }
    fclose(fin); fclose(fout);
    return 0;
}