#include <stdio.h>
#include <stdlib.h>

#define NMAX 100000

int v[NMAX];

int main()
{
  FILE *fin,*fout;
  fin=fopen("cautbin.in","r");
  fout=fopen("cautbin.out","w");

  int st,dr,n,x,m,p,mij=0,i,j;
  fscanf(fin,"%d",&n); ///nr de elemente din vector
  for(i=0;i<n;i++){
    fscanf(fin,"%d",&v[i]); ///sirul de nr
  }
  fscanf(fin,"%d",&m); ///nr de intrebari
  for(i=0;i<m;i++){
    fscanf(fin,"%d%d",&p,&x); ///tipul de intrebare si x ul

    if(p==0){
      st=0;
      dr=n-1;

      while(st<dr){ /// cautam binar catre ultima aparitie
        mij=(st+dr)/2+1;
        if(x>=v[mij])
          st=mij;
        else
          dr=mij-1;
      }
      if(x==v[st])
        fprintf(fout,"%d\n",st+1);
      else
        fprintf(fout,"-1\n");
    }

    else if(p==1){
      st=0;
      dr=n-1;

      while(st<dr){ /// cautam binar catre ultima aparitie
        mij=(st+dr)/2+1;
        if(x>=v[mij])
          st=mij;
        else
          dr=mij-1;
      }
      fprintf(fout,"%d\n",st+1);
    }
    else if(p==2){
      st=0;
      dr=n-1;

      while(st<dr){ /// cautam binar catre prima aparitie
        mij=(st+dr)/2;
        if(x<=v[mij])
          dr=mij;
        else
          st=mij+1;
       }
       fprintf(fout,"%d\n",st+1);
      }
    }

  fclose(fin);
  fclose(fout);
  return 0;
}