#include<stdio.h>
FILE *in,*out;
int st,dr,v[100002],i,nr,m,n,mij,caz;
int binara(int caz,int nr,int st,int dr)
{

   switch(caz)
   {


        case 0:
        {
            if(st>dr)
            {
                fprintf(out,"%d\n",-1);
                return 0;
            }
            mij=(st+dr)/2;
            if(nr==v[mij])
            {
                fprintf(out,"%d\n",mij);
                return 0;
            }
            else
                if(nr>v[mij])
                    binara(caz,nr,mij+1,dr);
                else
                    binara(caz,nr,st,mij-1);
            break;
        }

        case 1:
        {
            if(st>dr)
            {
                fprintf(out,"%d\n",dr);
                return 0;
            }
            mij=(st+dr)/2;
            if(v[dr]==nr)
            {
                    fprintf(out,"%d\n",dr);
                    return 0;
            }
            else
                if(v[st]==nr)
                {
                    fprintf(out,"%d\n",st);
                    return 0;
                }
                else
                    if(nr==v[mij])
                {
                    fprintf(out,"%d\n",mij);
                    return 0;
                }
                else

                if(nr>v[mij])
                    binara(caz,nr,mij+1,dr);
                else
                    binara(caz,nr,st,mij-1);
            break;
        }
        case 2:
        {
            if(st>dr)
            {
                fprintf(out,"%d\n",st);
                return 0;
            }
            mij=(st+dr)/2;

                if(nr==v[mij] && v[mij-1]!=nr)
                    {
                        fprintf(out,"%d\n",mij);
                        return 0;
                    }
                    else
            if(v[st]==nr)
            {
                fprintf(out,"%d\n",st);
                return 0;
            }
            else
                if(v[dr]==nr)
                {
                    fprintf(out,"%d\n",dr);
                    return 0;
                }
                else
                        if(nr>v[mij])
                            binara(caz,nr,mij+1,dr);
                        else
                            binara(caz,nr,st,mij-1);
                    break;
                }
   }
}


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%d",&caz,&nr);
        binara(caz,nr,1,n);
    }

    return 0;



}