#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");

int v[100005];

inline bool cmp(int poz, int x, int c){
  if(c < 2)
    return v[poz] <= x;
  return v[poz] < x;
}

int main()
{
  int n, rez, c, x, k;
  fi >> n;
  for(int i = 1; i <= n; i++)
    fi >> v[i];
  fi >> k;
  for(; k > 0; k--){
    fi >> c >> x;
    rez = 0;
    for(int pas = 1 << 20; pas > 0; pas /= 2)
      if(rez + pas <= n && cmp(rez + pas, x, c))
        rez += pas;
    if(c == 0 && v[rez] != x)
      fo << -1 << '\n';
    else if(c == 0 || c == 1)
      fo << rez << '\n';
    else
      fo << rez + 1 << '\n';
  }
  fi.close();
  fo.close();
  return 0;
}