#include <iostream>
#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;
	
	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--;
	
	if(v[mid] == val)
		return mid;
	return -1;
}

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;
	
	return -1;
}

int main () 
{   int n,x,tip,var;
	freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
	{
		 scanf("%d", &v[i]);
    }   scanf("%d", &x);
   while(x)
   {
	    
	    scanf("%d", &tip);
		scanf("%d", &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));
	x--;
		   
   }
		


	return 0;


}