#include<stdio.h>
#include<conio.h>

int N,M,*a;
FILE *pin;

inline void pregateste()
{
pin=fopen("cautbin.in","r");
fscanf(pin,"%d",&N);
a=new int[N+1];
for(int i=1;i<=N;i++)
  fscanf(pin,"%d",a+i);
}

int CautareBinara0(int element)
{
int li=1,ls=N,poz;
bool gasit=0;
while(!gasit && li<=ls)
  {if(ls%2)
    poz=li/2+(ls+1)/2;
  else
    poz=li/2+ls/2;
  if(a[poz]==element)
    gasit=1;
  else
    if(a[poz]>element)
      ls=poz-1;
    else if(a[poz]<element)
      li=poz+1;
  }
if(!gasit)
  return -1;
else
  {
  while(poz<N && a[poz+1]==element)
    poz++;
  return poz;
  }
}

int CautareBinara1(int element)
{
int li=1,ls=N,poz;
int last;
while(li<=ls)
  {
  if(ls%2==0)
    poz=li/2+ls/2;
  else
    poz=li/2+(ls+1)/2;
  if(a[poz]>element)
    ls=poz-1;
  else
    if(a[poz]<=element)
      {last=poz;
      li=poz+1;}
  }
return last;
}

int CautareBinara2(int element)
{clrscr();
printf("el=%d\n",element);
int li=1,ls=N,poz;
while(li<=ls)
  {
  if(ls%2==0)
    poz=li/2+ls/2;
  else
    poz=li/2+(ls+1)/2;
  printf("li=%d ls=%d\n",li,ls);getch();
  if(a[poz]==element) return poz;
  if(a[poz]<=element)
    li=poz+1;
  else
    if(a[poz]>element)
      ls=poz-1;
  }
}

inline void rezolva()
{
FILE *pout=fopen("cautbin.out","w");
fscanf(pin,"%d",&M);
int a,b;
for(int i=1;i<=M;i++)
  {
  fscanf(pin,"%d",&a);
  fscanf(pin,"%d",&b);
  if(a==0)
    fprintf(pout,"%d\n",CautareBinara0(b));
  if(a==1)
    fprintf(pout,"%d\n",CautareBinara1(b));
  if(a==2)
    fprintf(pout,"%d\n",CautareBinara2(b));
  }

fclose(pout);
}

inline void finalizeaza()
{delete []a;
fclose(pin);}

int main()
{
pregateste();
rezolva();
finalizeaza();
return 0;
}