#include <stdio.h>
#include <stdlib.h>
#define N 100010
int v[N];



int cautBin0 (int ls, int ld, int val)   // 0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
{
    int mid;
 
    while (ls <= ld) {
        mid = (ls + ld) / 2;
        if (v[mid] <= val)
            ls = mid + 1;
        else
            ld = mid - 1;
    }
    mid = (ls + ld) / 2;
 
    if (v[mid] > val) mid --;
    if (v[mid] == val)
        return mid;
    return -1;
}

int cautBin1 (int ls, int ld, int val)  //1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x 
{
	int mid, n = ld;
	
	while (ls < ld)
	{
		mid = (ls+ld)/2;
		if(v[mid] <= val)
			ls=mid+1;
		else
			ld = mid;
	}
	mid = (ls+ld)/2;
	
    if(v[mid] > val) 
		mid--;
	return mid;
}

int cautBin2 (int ls, int ld, int val) //2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
{
	int mid;
	
	while(ls < ld)
	{
		mid = (ls + ld)/2;
		if(v[mid] >= val)
			ld=mid-1;
		else
			ls=mid+1;
	}
	mid = (ls+ls)/2;
	if(v[mid] < val)
		mid++;
	return mid;
	
}

int main () 
{   int i,n,x,tip,var;
	
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
	
    scanf("%d", &n);
    for ( i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
     
   scanf("%d", &x);
  
   while(x -- )
   {
		scanf("%d%d", &tip, &var);
		if(tip == 0)
			printf("%d\n", cautBin0(1,n,var));
		if(tip == 1)
			printf("%d\n", cautBin1(1,n,var));
		if(tip == 2)
			printf("%d\n", cautBin2(1,n,var)); 
   }

	exit(0);


}