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

using namespace std;

/*
 * Robeta - "https://github.com/stoianmihail/Robeta"
 * Further improvements comes next, just check up the repository.
 * The code has been initially released under "https://github.com/learnedsystems/SOSD"
 * PS: Parsing the input was really necessary.
 */

static constexpr uint32_t MAX_N = 100000;
static constexpr uint32_t globalRho = 18;

static constexpr uint32_t IN_BUFFER_SIZE = 32768;
static constexpr uint32_t OUT_BUFFER_SIZE = 7e5;
char buffer[OUT_BUFFER_SIZE], *writeHead = buffer;

__attribute__((always_inline)) uint32_t getNumber();
__attribute__((always_inline)) void putNumber(int32_t x);
	
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();
    putNumber(lookup(type, x));
  }
  fwrite(buffer, 1, writeHead - buffer, stdout);
  return 0;
}

__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;	
}

__attribute__((always_inline)) void putNumber(int32_t x) {
  if (!x) {
    *(writeHead++) = 48;
    *(writeHead++) = 10;
    return;
  }
  if (x < 0) {
    *(writeHead++) = 45;
    *(writeHead++) = 49;
    *(writeHead++) = 10;
    return;
  }
  char *old = writeHead;
  while (x) {
    *(writeHead++) = x % 10 + 48;
    x /= 10;
  }
  std::reverse(old, writeHead);
  *(writeHead++) = 10;	
}