#include <cstdio>
using namespace std;

int binKer_0(long a[], long x, int n)
{
    int bal = 1, jobb = n;

    while (bal < jobb) {
        int k = (bal+jobb+1)/2;

        if(x<a[k]) jobb=k-1;
        else bal = k;
    }

	// bal == jobb

	return a[bal] == x ? bal : -1;
}


int binKer_1(long a[], long x, int n)
{
    int bal=1, jobb=n;

    while(bal<jobb){
        int k = (bal+jobb+1)/2;

        if(a[k]>x) jobb = k-1;
        else bal = k;
    }

    return bal;
}

int binKer_2(long a[], long x, int n)
{
    int bal=1, jobb=n;

    while(bal<jobb){
        int k=(bal+jobb)/2;

        if(a[k]<x) bal = k+1;
        else jobb = k;
    }

    return bal;
}

int main()
{
    FILE *in = fopen("cautbin.in", "r");
    FILE *out = fopen("cautbin.out", "w");

    int n, m;
    long x, l;

    fscanf(in, "%d", &n);

    long a[n+1];
    for(int i=1; i<=n; i++) fscanf(in, "%ld", &a[i]);

    fscanf(in, "%d", &m);
    for(int i=1; i<=m; i++){
        fscanf(in, "%ld %ld", &l, &x);
        if(l==0) fprintf(out, "%d\n", binKer_0(a, x, n));
        if(l==1) fprintf(out, "%d\n", binKer_1(a, x, n));
        if(l==2) fprintf(out, "%d\n", binKer_2(a, x, n));
    }

    return 0;
}