#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, tar;

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

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

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

		return sol;
}		
			

int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		
		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;
		
}