#include <stdio.h>
#include <bits/stdc++.h>
 
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i = a; i < b; i++)
 
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

 
ifstream fi ("cautbin.in");
ofstream fo ("cautbin.out");
 
 
int N, M, q, x, a[100555];
 
int main() 
{
	fi >> N;
  
	for(int i = 0; i < N; i++)
	fi >> a[i];
 
  	fi >> M;
  	while(M--) 
	{
	    fi >> q >> x;
	    int pos = -2;
	 
		switch(q)
		{
			case 0 :pos = upper_bound(a, a+N, x)-a-1;
		    	 	if (pos < 0 || a[pos] < x) pos = -2;
		    	 	break;
		   	case 1 :pos = upper_bound(a, a+N, x)-a-1;
		   			break;
		   	case 2 :pos = lower_bound(a, a+N, x)-a;
		   			break;
		   	default : continue;		
		}
	    
	    fo << pos + 1 << '\n';
 	}
 
  
}