#include <fstream>
#include <iostream>
using namespace std;
int n,a[100001];


inline int BS1(int x)
{
    int lo, hi, mid;
 
    for (lo = 1, hi = n; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (x < a[mid]) hi = mid-1;
        else if (a[mid] < x) lo = mid+1;
        else return mid;
    }
    return -1;
}

inline int BS2(int x)
{
    int lo, hi, mid, last = 0;
 
    for (lo = 1, hi = n; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (a[mid] <= x) last = mid, lo = mid+1;
        else hi = mid-1;
    }
    return last;
}
 
inline int BS3(int x)
{
    int lo, hi, mid, last = n+1;
 
    for (lo = 1, hi = n; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (x <= a[mid]) last = mid, hi = mid-1;
        else lo = mid+1;
    }
    return last;
}


inline int f0(int x){
	int st=1,dr=n,rez = -1;
	while(st<=dr){
		int m = st+(dr-st)/2;
//		cout<<m<<" ";
		if( a[m] == x)
			 rez = m;
		if(a[m]<x)
				 st = m+1;
		else
			dr= m-1;
	}
	return rez;
}
inline int f1(int x){
	int st=1,dr=n,rez;
	while(st<=dr){
		int m = st+(dr-st)/2;
		if(a[m]<=x)
			rez = m, st= m+1;
		else
			dr = m-1;
	}
	return rez;
}
inline int f2(int x){
	int st=1,dr=n, rez;
	while(st<=dr){
		int m =st+(dr-st)/2;
		if(a[m]>=x)
			rez = m , dr = m-1;
		else
			st = m+1;

	}
	return rez;
}
int main(){
	ifstream fin("cautbin.in");
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>a[i];
	int m;
	fin>>m;
	ofstream fout("cautbin.out");
/*	for( ; m ; --m){
		int c,x;
		fin>>c>>x;
		switch(c){
//			case 0:{fout<<f0(x)<<endl;break;}
			case 0:{fout<<BS1(x)<<endl;break;}
			
//			case 1:{fout<<f1(x)<<endl;break;}
			case 1:{fout<<BS2(x)<<endl;break;}
			
//			case 2:{fout<<f2(x)<<endl;break;}
			case 2:{fout<<BS3(x)<<endl;break;}
		}
	}
	* */
	int c, x;
	for (; m; --m)
	{
		fin >> c >> x;
		if (c == 0)
			fout << BS1(x);
		else
			if (c == 1)
				fout << BS2(x);
			else
				fout << BS3(x);
	}
	fout.close();
	return 0;
}