#include <fstream>
using namespace std;
int v[100000], n, s, d, m, ma;

int f0(int a)
{
    s=1;
	d=n;
    while(s<d){
        ma=m;
        m=(s+d)/2;
        if(ma==m)
			break;
        if(v[m]<=a)
			s=m;
        else 
			d=m-1;}
	while(v[d]>a)
		d--;
    if(v[d]==a)
		return d;
    return -1;
}

int f1(int a)
{
    s=1;
	d=n;
    while(s<d){
        ma=m;
        m=(s+d)/2;
        if(ma==m)
			break;
        if(v[m]<=a)
			s=m;
        else
			d=m-1;}
    while(v[d]>a)
		d--;
    return d;

}

int f2(int a)
{
    s=1;
	d=n;
    while(s<d){
        m=(s+d)/2;
        if(v[m]<a)
			s=m+1;
        else 
			d=m;}
    if(v[s]<a)
		s++;
    return s;
}

int main()
{
    ifstream in ("cautbin.in");
    ofstream out ("cautbin.out");
    int i, m, f, e;
    in>>n;
    for(i=1;i<=n;++i) 
		in>>v[i];
    in>>m;
    for(i=1;i<=m;++i){
		in>>f>>e;
		switch(f){
		case 0:
			out<<f0(e)<<'\n';
			break;
		case 1:
			out<<f1(e)<<'\n';
			break;
		case 2:
			out<<f2(e)<<'\n';
			break;
		default:
			break;}}
    return 0;
}