#include<cstdio>
#include<algorithm>
#include<fstream>
#define dim 100100
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,i,j,q,x,y;
int a[dim];
int k;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
		f>>a[i];
    f>>q;
	for(;q;--q)
    {
        f>>x>>y;
        if(y==0)
        {
            k=upper_bound(a+1, a+n+1, x)-a-1;
            if(a[k]==x)
				g<<k<<"\n";
            else
				g<<-1<<"\n";
        }
        else 
			if(y==1)
			{
				k=lower_bound(a+1, a+n+1, x+1)-a-1;
				g<<k<<"\n";
			}
        else
        {
            k=upper_bound(a+1, a+n+1, x-1)-a;
            g<<k<<"\n";
        }
    }
	return 0;
}