#include <fstream.h>
#define max 1000000
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[max];
int cb0(int x, int a, int b){
    int m;
    while(a<=b){
                m=(a+b)/2;
                if(v[m]<=x)
                a=m+1;
                else b=m-1;
}
m=(a+b)/2;
if(v[m]>x) m--;
if(v[m]==x) return m;
return -1;
}
int cb1(int x,int a,int b)
{
    int m;
    while (a < b){
        m = (a + b) / 2;
        if (v[m] <= x)
            a = m + 1;
        else b = m;
    }

    m = (a + b) / 2;
    if (v[m] > x)
       -- m;
    return m;
}
int cb2(int x, int a, int b)
{
    int m;
	while(a<b)
	{
		m=(a+b)/2;
		if(v[m]<x)
			a=m+1;
		else b=m;
	}
	
	m=(a+b)/2;
	if(v[m]<x)
		m++;
	return m;
}
int main(){
    int n,m,x,y;
    f>>n;
    for(int i=1;i<=n;i++) f>>v[i];
    f>>m;
    while(m--){
               f>>y>>x;
               if(y==0) g<<cb0(x,1,n)<<"\n";
               if(y==1) g<<cb1(x,1,n)<<"\n";
               if(y==2) g<<cb2(x,1,n)<<"\n";
             }
}