#include <iostream>
#include <fstream>
using namespace std;

#define nmax 100002

int v[nmax] ,n ;

int cautareBinara0( int val)  {
    int el = 0,ve = n-1, mid;
    while (el <= ve ) {
        mid = (el + ve) / 2;
        if (v[mid] <= val)  el = mid+1;
        else                ve = mid-1;
    }
    mid = (el+ve)/2;
    if (v[mid] > val) mid--;
    if (v[mid] == val) {
        return mid
    }
    return -1;
}

int cautareBinara1( int val)  {
    int el = 0,ve = n-1, mid;
    while (el < ve ) {
        mid = (el + ve) / 2;
        if (v[mid] <= val)  el = mid+1;
        else               ve = mid-1;
    }
    mid = (el+ve)/2;
    if (v[mid] > val) mid--;
    return mid;
}

int cautareBinara2( int val)  {
    int el = 0,ve = n-1, mid;
    while (el < ve ) {
        mid = (el + ve) / 2;
        if (v[mid] < val)  el = mid+1;
        else               ve = mid-1;
    }
    mid = (el+ve)/2;
    if (v[mid] < val) mid++;
    return mid;
}

int main()
{
    freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
    int m ;
	scanf("%d",&n);
	for ( int i = 0; i<n; i++ ) {
        scanf("%d",&v[i]);
	}
	scanf("%d",&m);

	int a,b;
	for ( int intrebari = 0; intrebari<m; intrebari++ ) {
        scanf("%d %d",&a, &b);

        if (a==0) {
            printf("%d\n",cautareBinara0(b));
        }
        else if (a==1) {
             printf("%d\n",cautareBinara1(b));
        }
        else {
            printf("%d\n",cautareBinara2(b));
        }
	}
	fclose(stdin);
	fclose(stdout);
    return 0;
}