#include<cstdio>
using namespace std;

const char in[]="cautbin.in";
const char out[]="cautbin.out";

const int N = 100005;

int v[N], n, m, op;

int zero(int tar)
	{
		int lo = 1, hi = n, mid;
		
		while(lo <= hi)
		{
			mid = (lo + hi) / 2;
		
			//if(v[mid] == tar)return mid;//sol = mid, lo = mid + 1;
			if(v[mid] <= tar) lo = mid + 1;
			else hi = mid - 1;
			
		}
		mid = (lo + hi)/2 ;
		if(v[mid] > tar) --mid;
		if(v[mid] == tar)return mid;
	
		return -1;
}

int unu(int tar)
	{
		int lo = 1, hi = n, mid;
		
		while(lo < hi)
		{
			mid = (lo + hi) / 2;
		
			if(v[mid] <= tar)lo = mid + 1;
			else hi = mid;
		}
		mid = (lo + hi)/ 2;
		if(v[mid] > tar)--mid;
		return mid;
}

int doi(int tar)
	{
		int lo = 1, hi = n, mid;
	
		while(lo < hi)
		{
			mid = (lo + hi) / 2;
	
			if(v[mid] < tar)lo = mid + 1;
			else hi = mid;
		}	
		
		mid = (lo + hi) / 2;
		if(v[mid] < tar)++mid;
		
		return mid;
}		
			

int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		int tar;
		scanf("%d", &n);
		
		for(int i = 1 ; i <= n ; ++i)
			scanf("%d", &v[i]);
		
		scanf("%d", &m);
		
		for(int i = 1 ; i <= m ; ++i)
		{
			scanf("%d %d", &op, &tar);
			if(!op)printf("%d\n", zero(tar));
			else if(op == 1)printf("%d\n", unu(tar));
			else printf("%d\n", doi(tar));
		}
		
		return 0;
		
}