#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <cstdio>

using namespace std;

#define MAX_N 100000
static constexpr uint32_t globalRho = 18;

#define IN_BUFFER_SIZE 8196
	
__attribute__((always_inline)) uint32_t getNumber() {
  static char inBuffer[IN_BUFFER_SIZE];
  static int p = IN_BUFFER_SIZE - 0x1;
  uint32_t number = 0x0;
  while ((inBuffer[p] < 0x30) || (inBuffer[p] > 0x39)) {	
    ++p == IN_BUFFER_SIZE && (fread(inBuffer, 0x1, IN_BUFFER_SIZE, stdin), p = 0x0);
  }
	
  for (;;) {
    number = number * 0xA + inBuffer[p] - 0x30;
    ++p == IN_BUFFER_SIZE && (fread(inBuffer, 0x1, IN_BUFFER_SIZE, stdin), p = 0x0);
    if ((inBuffer[p] < 0x30) || (inBuffer[p] > 0x39))
      break;
  }
  return number;	
}

uint32_t n, globalMin, globalMax, globalOccupied, globalShiftWith;
uint32_t keys[MAX_N];
uint32_t radixHint[(1u << globalRho) + 1];

void buildSimpleRadix() {
  uint32_t lastPrefix = 0;
  for (unsigned index = 0; index != n; ++index) {
    uint32_t currPrefix = (keys[index] - globalMin) >> globalShiftWith;
    if (currPrefix == lastPrefix)
      continue;
    for (unsigned prefix = lastPrefix + 1; prefix <= currPrefix; ++prefix)
      radixHint[prefix] = index;
    lastPrefix = currPrefix;
  }
  for (; lastPrefix != (1u << globalRho); ++lastPrefix)
    radixHint[lastPrefix + 1] = n;
}

inline int32_t lookup(const uint32_t type, const uint32_t x) {
  if ((type == 0) && (x < globalMin))
    return -1;
  if ((type == 1) && (x >= globalMax))
    return n;
  if ((type == 2) && (x <= globalMin))
    return 1;
  
  uint32_t prefix = (x - globalMin) >> globalShiftWith;
  uint32_t begin = radixHint[prefix], end = radixHint[prefix + 1];

  int32_t index = -1;
  switch (type) {
    case 0 : {
      index = upper_bound(keys + begin, keys + end, x) - keys - 1;
      if (keys[index] != x)
        return -1;
      break;
    }
    case 1 : {
      index = lower_bound(keys + begin, keys + end, x + 1) - keys - 1;
      break;
    }
    case 2 : {
      index = upper_bound(keys + begin, keys + end, x - 1) - keys;
      break;
    }
  }
  return index + 1;
}

int main() {
  freopen("cautbin.in", "r", stdin);
  
  n = getNumber();
  for (unsigned index = 0; index != n; ++index)
    keys[index] = getNumber();
  globalMin = keys[0];
  globalMax = keys[n - 1];
  globalOccupied = 32 - __builtin_clz(globalMax - globalMin);
  globalShiftWith = globalOccupied - globalRho;
  
  buildSimpleRadix();
  
  freopen("cautbin.out", "w", stdout);
  unsigned m = getNumber();
  while (m--) {
    unsigned type = getNumber(), x = getNumber();
    printf("%d\n", lookup(type, x));
  }
  return 0;
}