#include <fstream>
using namespace std;

int answerQ0(int *vect, int low, int high, int val);
int answerQ1(int *vect, int low, int high, int val);
int answerQ2(int *vect, int low, int high, int val);

int main(void)
{
  int n, m, i, qType, qVal;
  int *vect;

  ifstream f("cautbin.in");
  ofstream g("cautbin.out");

  f >> n;
  vect = new int[n];
  for (i=0;i<n;i++)
  {
    f >> vect[i];
  }

  f >> m;
  for (i=0;i<m;i++)
  {
    f >> qType;
    f >> qVal;

    switch(qType)
    {
    case 0:
      g << answerQ0(vect,0,n-1,qVal)+1 << "\n";
      break;
    case 1:
      g << answerQ1(vect,0,n-1,qVal)+1 << "\n";
      break;
    case 2:
      g << answerQ2(vect,0,n-1,qVal)+1 << "\n";
      break;
    }
  }
  
  f.close();
  g.close();
  delete[] vect;
  return 0;
}

int answerQ0(int *vect, int low, int high, int val)
{
  int mid;
  while (low <= high)
  {
    mid = low + (high-low)/2;
    if (vect[mid] <= val)
    {
      low = mid+1;
    }
    else high = mid-1;
  }

  if (vect[low-1] == val) return low-1;
  else return -2;
}

int answerQ1(int *vect, int low, int high, int val)
{
  int mid;
  while (low <= high)
  {
    mid = low + (high-low)/2;
    if (vect[mid] <= val)
    {
      low = mid+1;
    }
    else high = mid-1;
  }
  return low-1;
}

int answerQ2(int *vect, int low, int high, int val)
{
  int mid;
  while (low <= high)
  {
    mid = low + (high-low)/2;
    if (vect[mid] < val)
    {
      low = mid+1;
    }
    else high = mid-1;
  }
  return low;
}