#include <bits/stdc++.h>
using namespace std;

int n,m,i,x,y,a[100100];

int main(){
	ifstream cin ("cautbin.in");
	ofstream cout ("cautbin.out");
	cin>>n;
	for (i=1; i<=n; i++) cin>>a[i];
	cin>>m;
	for (i=1; i<=m; i++){
		cin>>x>>y;
		if (x==0){
			if (a[n]<y) cout<<"-1";
			else if (a[1]>y) cout<<"-1";
			else {
				int st=1, dr=n, mid=st+ (dr-st)/2;
				while (dr-st>1){
					if (y>=a[mid]){
						st=mid; mid=st+ (dr-st)/2;
					}
					else {
						dr=mid-1; mid=st+(dr-st)/2;
					} 
				}
				if(a[dr]==y) cout<<dr;
				else if (a[st]==y) cout<<st;
				else cout<<"-1";
			}
		}
		else if (x==1){
			int st=1, dr=n, mid=st+ (dr-st)/2;
			while (dr-st>1){
				if (y>=a[mid]){
					st=mid; mid=st+ (dr-st)/2;
				}
				else {
					dr=mid-1; mid=st+(dr-st)/2;
				} 
			}
			if(a[dr]<=y) cout<<dr;
			else cout<<st;
		}
		else {
			int st=1, dr=n, mid=st+ (dr-st)/2;
				while (dr-st>1){
					if (y>a[mid]){
						st=mid; mid=st+ (dr-st)/2;
					}
					else {
						dr=mid; mid=st+(dr-st)/2;
					} 
				}
				if (a[st]>=y) cout<<st;
				else cout<<dr;
		}
	}
	return 0;
}