#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N,v[500000];

int main()
{
    int i,M,a,b,poz;
    poz=-1;
    f>>N;
    for(i=1;i<=N;i++)
        f>>v[i];

    f>>M;
    for(i=1;i<=M;i++)
    {
        f>>a>>b;

        int mij;
        int st=0;
        int dr=N;
        int ok=0;

        while((ok==0)&&(st<=dr))
        {
            mij=st+(dr-st)/2;

            if(v[mij]<b)
                st=mij+1;

            if(v[mij]==b)
                ok=1;

            if(v[mij]>b)
                dr=mij-1;

        }
        if(ok==1)
          {
            while(v[mij+1]==b)
             mij=mij+1;
            poz=mij;
          }
        else
            poz=-1;


      if(b==0)
      {
        if((a==0)&&(v[1]>0))
           g<<-1<<'\n';
        if(((a==0)||(a==2))&&(v[1]==0))
            {
             int x=1;
             while(v[x]==0)
                {poz=x;
                x=x+1;}
             g<<poz<<'\n';
            }
        if((a==2)&&(v[1]>0))
             g<<1<<'\n';

      }
      else
      {
       if(a==0)
          g<<poz<<'\n';

       if((a!=0)&&(poz!=-1))
          g<<poz<<'\n';

       if((a==1)&&(poz==-1))
          g<<dr<<'\n';

       if((a==2)&&(poz==-1))
          g<<st<<'\n';
      }

    }


    return 0;
}