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

int *v;
int N,M;

int rez_max(int x)
{
  while(v[x+1]==v[x])x++;
  return x+1;
}
int rez_min(int x)
{
  while(v[x-1]==v[x])x--;
  return x+1;
}

int f1(int i,int fdiv,int val)
{
  if(i>=N)return f1(i-fdiv,fdiv>>1,val);
  if(v[i]==val)return rez_max(i);
  if(fdiv==0)return -1;
  if(v[i]>val)return f1(i-fdiv,fdiv>>1,val);
  return f1(i+fdiv,fdiv>>1,val);
}

int f2(int i,int fdiv,int val)
{
  if(i>=N)return f2(i-fdiv,fdiv>>1,val);
  if(v[i]==val)return rez_max(i);
  if(fdiv==0){
    while(v[i]<val)i++;
    return rez_max(i);
  }
  if(v[i]>val)return f2(i-fdiv,fdiv>>1,val);
  return f2(i+fdiv,fdiv>>1,val);
}

int f3(int i,int fdiv,int val)
{
  if(i>=N)return f3(i-fdiv,fdiv>>1,val);
  if(v[i]==val)return rez_min(i);
  if(fdiv==0){
    while(v[i]>val)i--;
    return rez_min(i);
  }
  if(v[i]<val)return f3(i+fdiv,fdiv>>1,val);
  return f3(i-fdiv,fdiv>>1,val);
}

int init(int x,int y)
{
  int aux=1;
  while(aux<=N)aux=aux<<1;
  aux=aux>>1;
  switch(y){
  case 0:
    return f1(aux-1,aux>>1,x);
  case 1:
    return f2(aux-1,aux>>1,x);
  case 2:
    return f3(aux-1,aux>>1,x);
  }
}

int main()
{
  FILE*fin,*fout;
  fin=fopen("cautbin.in","r");
  fout=fopen("cautbin.out","w");
  
  fscanf(fin,"%d",&N);
  v=(int*)malloc(N*sizeof(int));
  int i;
  for(i=0;i<N;i++){
    fscanf(fin,"%d",&v[i]);
  }
  
  fscanf(fin,"%d",&M);
  for(i=0;i<M;i++){
    int x,y;
    fscanf(fin,"%d %d",&y,&x);
    fprintf(fout,"%d\n",init(x,y));
  }
  fclose(fin);
  fclose(fout);
}