#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *in,*out;
int n,i,m,type,poz,v[100001],var;
int main()
{
    in=fopen("cautbin.in","rt");
    out=fopen("cautbin.out","wt");
    fscanf(in,"%d",&n);

    for(i=1;i<=n;i++)
        fscanf(in,"%d",&v[i]);

    fscanf(in,"%d",&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d",&type);
        fscanf(in,"%d",&var);
        if(type==0)
        {
            poz=upper_bound(v+1,v+n+1,var)-v-1;
            if(v[poz]!=var)
                fprintf(out,"-1");
            else
                fprintf(out,"%d\n",poz);
        }
        if(type==1)
        {
            poz=upper_bound(v+1,v+n+1,var)-v-1;
            fprintf(out,"%d\n",poz);
        }
        if(type==2)
        {
            poz=lower_bound(v+1,v+n+1,var)-v;
            fprintf(out,"%d",poz);
        }
    }
    fclose(in);
    fclose(out);
    return 0;
}