#include <stdio.h>
int v[100000];
inline int cbin(int x,int n)
{
    int ls,ld,mij;
    ls=0;ld=n-1;
    while(ls<=ld)
    {
        mij=(ls+ld)/2;
        if(x==v[mij])
            return mij;
        if(x<v[mij])
            ld=mij-1;
        else
            ls=mij+1;
    }
    return ls-1;
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("cautbin.in","r");
    fout=fopen("cautbin.out","w");
    int m,n,i,x,poz,p;
    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++)
        fscanf(fin,"%d",&v[i]);
    fscanf(fin,"%d",&m);
    for(i=0;i<m;i++)
    {
        fscanf(fin,"%d%d",&p,&x);
        poz=cbin(x,n);
        if(v[poz]!=x)
        {
            if(!p)
                fprintf(fout,"-1\n");
            else
                if(p==1)
                    fprintf(fout,"%d\n",poz+1);
            else
                fprintf(fout,"%d\n",poz+2);
        }
        else
        {
            if(p==2)
                while(v[poz]==v[poz-1])
                    poz--;
            else
                while(v[poz]==v[poz+1])
                    poz++;
            fprintf(fout,"%d\n",poz+1);
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}