#include <stdio.h>
long v[1001],i,m,n,x,y;
long cauta1(long st,long dr)
{long mij=st+(dr-st)>>2;
 if(st==dr){if(v[st]==x)return st;else return -1;}
      else
       if(v[mij+1]>x)return cauta1(st,mij);
	      else return cauta1(mij+1,dr);
}

long cauta3(long st,long dr)
{long mij=st+(dr-st)>>2;
 if(st==dr)return st;  else
       if(v[mij+1]>x)return cauta3(st,mij);
	      else return cauta3(mij+1,dr);
}

long cauta2(long st,long dr)
{long mij=st+(dr-st)>>2;
 if(st==dr)return st;  else
       if(v[mij]<x)return cauta2(mij+1,dr);
	      else return cauta2(st,mij);
}

int main()
{freopen("cautbin.in","r",stdin);freopen("cautbin.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;i++)scanf("%ld",&v[i]);
 scanf("%ld",&m);
 for(i=1;i<=m;i++)
  {scanf("%ld%ld",&y,&x);
   if(y==0)printf("%ld\n",cauta1(1,n));
    else
   if(y==1){printf("%ld\n",cauta3(1,n));}
    else printf("%ld\n",cauta2(1,n));
  }
 fclose(stdin);fclose(stdout);
 return 0;
}