using namespace std;

#include <iostream>
#include <fstream>
const int N=100000;
int m,n,p,u,T,k,h,v[N];

int cautare(int x, int tip){
	p=1;
	u=n;
	while(p!=u)
	{
		m=p + (u-p)/2;
		if(x<=v[m])
			u=m;
		else 
			p=m+1;
	}
	if(tip==0)
	{
		if(x!=v[p])
			return -1;
		return p;
	}
	if(tip==1)
	{
		if(v[p]>x)
			--p;
		return p;
	}
	if(v[p]<x)
		++p;
	return p;
}

int main(){
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(int i=1;i<=n;++i)
		f>>v[i];
	f>>T;
	while(T--)
	{
		f>>h;
		f>>k;
		g<<cautare(k,h)<<"\n";
	}
	return 0;
}