#include <fstream>
 #include<iostream>
using namespace std;
 
ifstream f("cautbin.in");
ofstream g("cautbin.out");
 
int n,  v[100001];
 
int bs0(int x, int st, int dr)
{
    
    int med=(st+dr)/2;
    if(st==dr)
        if(x==v[st]) 
			return med;
        else 
			return -1;
    else
    {
        if(x>=v[med+1])
			return bs0(x, med+1, dr);
        if(x>v[med])
			return -1;
        if(x==v[med])
			return med;
        if(med-1>=st) 
			return bs0(x, st, med-1);
        return -1;
    }
}
int bs1(int x, int st, int dr)
{
    int med=(st+dr)/2;
    if(st==dr) 
		return med;
    if(x>=v[med+1]) 
		return bs1(x, med+1, dr);
    if(x>=v[med])
		return med;
    return bs1(x, st, med-1);
}
int bs2(int x, int st, int dr)
{
    int med=(st+dr)/2;
    if(x<=v[med-1]) 
		return bs2(x, st, med-1);
    if(x<=v[med])
		return med;
    return bs2(x, med+1, dr);
}
int main()
{ int m,i,x,y;
    f>>n;
    for(i=1; i<=n; i++)
		f>>v[i];
    f>>m;
    for(i=1; i<=m; i++)
    {
        f>>y>>x;
        if(y==0) 
			g<<bs0(x, 1, n)<<'\n';
        else if(y==1)
                 g<<bs1(x, 1, n)<<'\n';
             else if(y==2)
				 g<<bs2(x, 1, n)<<'\n';
    }
	f.close();
	g.close();
	
    return 0;
}