#include<cstdio>
using namespace std;
int v[100001];
int cb0 (int p, int u, int key)
{   int m;
    while(p<=u) 
	{   m=(p+u)/2;
        if(v[m]<=key) p=m+1; else u=m-1;
    }
    m=(p+u)/2;
    if(key<v[m]) --m;
    if(key==v[m]) return m;
    return -1;
}
int cb1(int p, int u, int key) 
{   int m;
    while(p<u)
	{   m=(p+u)/2;
        if(v[m]<=key) p=m+1; else u=m;
    }
    m=(p+u)/2;
    if(key<v[m]) --m;
    return m;
}
int cb2 (int p, int u, int key) 
{   int m;
    while(p<u) 
	{   m=(p+u)/2;
        if(v[m]<key) p=m+1; else u=m;
    }
    m=(p+u)/2;
    if(v[m]<key) ++m;
    return m;
}
int main () 
{   int n,m,tip,val;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&v[i]);
    scanf("%d",&m);
    while(m--)
	{   scanf("%d%d",&tip,&val);
		if(tip==0) printf("%d\n",cb0(1,n,val));
		if(tip==1) printf("%d\n",cb1(1,n,val));
		if(tip==2) printf("%d\n",cb2(1,n,val));
    }
    return 0;
}