#include<fstream.h>

int v[100010],n,intrebari,x,i,s,d,m,sol,q;

int main()

{

ifstream f("cautbin.in");
ofstream g("cautbin.out");

f>>n;

for(i=1;i<=n;i++) f>>v[i];

f>>intrebari;

for(i=1;i<=intrebari;i++)

 { f>>q>>x; s=1; d=n;


   m=(s+d)>>1;

   if(q==0)

   {while(s<=d)

     { if(v[m]<x) s=m+1;

	 else if(v[m]>x) d=m-1;

	else break;

       m=(s+d)>>1;
      }
    if(s<=d) g<<m<<'\n'; else g<<"-1"<<'\n';}

     else if(q==1)

    { while(s<=d)

     { if(v[m]<=x) { s=m+1;sol=m;}

	 else  d=m-1;


       m=(s+d)>>1;
      }

     g<<sol<<'\n';
    }

     else

    { while(s<d&&s!=d-1)

     { if(v[m]>=x) {d=m-1;  sol=m;}

	 else s=m+1;

       m=(s+d)>>1;
      }
     g<<sol<<'\n';
   }

  }

f.close();
g.close();
return 0;
}