#include<stdio.h>
FILE*fin=fopen("cautbin.in","r");
FILE*fout=fopen("cautbin.out","w");
int n,m,s[100001];
int main()
{
  int i,o,x,st,dr,mij;
  fscanf(fin,"%d",&n);
  for(i=1;i<=n;i++)
    fscanf(fin,"%d",&s[i]);
  fscanf(fin,"%d",&m);
  for(i=1;i<=m;i++)
  {
    fscanf(fin,"%d%d",&o,&x);
    if(o==0)
    {
      st=1;dr=n;
      while(st<dr-1)
      {
	mij=(st+dr)/2;
	if(s[mij]<=x) st=mij;
	else dr=mij-1;
      }
      if(s[st]==x) fprintf(fout,"%d\n",st);
      else if(s[dr]==x) fprintf(fout,"%d\n",dr);
      else fprintf(fout,"-1\n");
    }
    if(o==1)
    {
      st=1;dr=n;
      while(st<dr-1)
      {
	mij=(st+dr)/2;
	if(s[mij]<=x) st=mij;
	else dr=mij-1;
      }
      if(s[dr]<=x) fprintf(fout,"%d\n",dr);
      else fprintf(fout,"%d\n",st);
    }
    if(o==2)
    {
      st=1;dr=n;
      while(st<dr)
      {
	mij=(st+dr)/2;
	if(s[mij]>=x) dr=mij;
	else st=mij+1;
      }
      fprintf(fout,"%d\n",st);
    }
  }
  fclose(fin);
  fclose(fout);
  return 0;
}