#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fi ("cautbin.in");
ofstream fo ("cautbin.out");

int A[100002],k,n;

int cb0 (int n,int x)
{
	int st=1,dr=n,m;
	while (st<dr)
	{
		m=(st+dr)/2;
		if(A[m]<=x)
			st=m+1;
		else dr=m-1;
	}
	m=(st+dr)/2;
	if(A[m]>x)m--;
	if(A[m]==x)
		return m;
	return -1;
}

int cb1 (int n,int x)
{
	int st=0,dr=n+1,m;
	while (st<dr)
	{
		m=(st+dr)/2;
		if(x>=A[m])
			st=m;
		else dr=m-1;
	}
    return st;
}

int cb2 (int n,int x)
{
	int st=1,dr=n,m;
	while (st<dr)
	{
		m=(st+dr)/2;
		if(x>A[m])
			st=m+1;
		else dr=m-1;
	}
	m=(st+dr)/2;
    if (A[m]<x)
       m++;
    return m;
}

int main ()
{
	fi>>n;
	for(int i=1;i<=n;i++)
		fi>>A[i];
	
	fi>>k;int x,y;
	for(int i=1;i<=k;i++)
	{
		fi>>x>>y;
		if(x==0) fo<<cb0(n,y)<<"\n";
		if(x==1) fo<<cb1(n,y)<<"\n";
		if(x==2) fo<<cb2(n,y)<<"\n";
	}
	fi.close();
	fo.close();
	return 0;
}