#include<stdio.h>

#define INPUT "cautbin.in"
#define OUTPUT "cautbin.out"
#define NMAX 100001

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long N;
long A[ NMAX ];

void readData()
{
  fscanf(fin, "%ld", &N);

  for(long i = 1; i <= N; ++i)
    fscanf(fin, "%ld", A+i);
}

long a_binary(long Value, long Left, long Right)
{
  long mid = (Left + Right) >> 1;

  if(Left > Right)
    return -1;

  if(A[ mid ] == Value)
    return mid;
  else
  if(A[ mid ] > Value)
    return a_binary(Value, Left, mid - 1);
  else
    return a_binary(Value, mid + 1, Right);
}

long b_binary(long Value, long Left, long Right)
{
  long mid = (Left + Right) >> 1;

  if(Left > Right)
    return mid;

  if(A[ mid ] == Value)
    return mid;
  else
  if(A[ mid ] > Value)
    return b_binary(Value, Left, mid - 1);
  else
    return b_binary(Value, mid + 1, Right);
}

long c_binary(long Value, long Left, long Right)
{
  long mid = (Left + Right) >> 1;

  if(Left > Right)
    return mid + 1;

  if(A[ mid ] == Value)
    return mid;
  else
  if(A[ mid ] > Value)
    return c_binary(Value, Left, mid - 1);
  else
    return c_binary(Value, mid + 1, Right);
}

void solve()
{
  long M, Code, Value;

  fscanf(fin, "%ld", &M);

  for(long i = 0; i < M; ++i)
  {
    fscanf(fin, "%ld %ld", &Code, &Value);

    if(Code == 0)
      fprintf(fout, "%ld\n", a_binary(Value, 1, N));
    else
    if(Code == 1)
      fprintf(fout, "%ld\n", b_binary(Value, 1, N));
    else
      fprintf(fout, "%ld\n", c_binary(Value, 1, N));
  }
}

int main()
{
  readData();

  solve();

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