#include<cstdio>
 
using namespace std;
 
int n,v[100005];
long maxstep=1<<17;
 
int bin0(int val)
{
    long step,i,temp;
    step = maxstep;
    for(i=0; step>0; step>>=1)
    {
        temp=i+step;
        if(temp<n && v[temp]<=val)
            i+=step;
    }
    if(v[i]==val) return 1+i;
    else return -1;
}
 
int bin1(int val)
{
    long step,i,temp;
    step = maxstep;
    for(i=0; step>0; step>>=1)
    {
        temp=i+step;
        if(temp<n && v[temp]<=val)
            i+=step;
    }
    return 1+i;
}
 
int bin2(int val)
{
    long step,i,temp;
    if(v[0]>=val) return 1;
    step = maxstep;
    for(i=n; step>0; step>>=1)
    {
        temp=i-step;
        if(temp>0) if(temp<n && v[temp]>=val)
            i-=step;
    }
    return 1+i;
}
 
 
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&v[i]);
     
 
    int m,a,t;
    scanf("%d",&m);
    for( ; m; --m)
    {
        scanf("%d %d",&t,&a);
        if(t==0) printf("%d\n",bin0(a));
        else if(t==1) printf("%d\n",bin1(a));
        else if(t==2) printf("%d\n",bin2(a));
    }
     
    return 0;
}