#include <fstream>
using namespace std;

ifstream cin ("cautbin.in");
ofstream cout("cautbin.out");

int n;
int v[100001];

int cautareBinara (int val)
{
  int stanga = 1, dreapta = n;
  while (stanga <= dreapta)
    {
      int mijloc = (dreapta + stanga) / 2;
      
      if (val == v[mijloc])
	  return mijloc;

      if (val < v[mijloc])
	dreapta = mijloc - 1;
      else
        stanga = mijloc + 1;
    }
  
  return -1;
}

void s1 (int val)
{
  cout << cautareBinara (val) << "\n";
}

int cautareBinara2 (int val, int &um)
{
  int stanga = 1, dreapta = n;
  while (stanga <= dreapta)
    {
      int mijloc = (dreapta + stanga) / 2;
      
      if (val == v[mijloc])
	  return mijloc;

      if (val < v[mijloc])
	dreapta = mijloc - 1;
      else
	{
	  um = mijloc;
	  stanga = mijloc + 1;
	}
    }
  
  return -1;
}

void s2 (int val)
{
  int ultimul_mijloc = 0;
  int cautareBin = cautareBinara2(val, ultimul_mijloc);
  if (cautareBin == -1)
    cout << ultimul_mijloc << "\n";
  else
    cout << cautareBin << "\n";
}

int cautareBinara3 (int val, int &um)
{
  int stanga = 1, dreapta = n;
  while (stanga <= dreapta)
    {
      int mijloc = (dreapta + stanga) / 2;
      
      if (val == v[mijloc])
	  return mijloc;

      if (val < v[mijloc])
	{
	  um = mijloc;
	  dreapta = mijloc - 1;
	}
      else
	stanga = mijloc + 1;
    }
  
  return -1;
}

void s3 (int val)
{
  int ultimul_mijloc = 0;
  int cautareBin = cautareBinara3(val, ultimul_mijloc);
  if (cautareBin == -1)
    cout << ultimul_mijloc << "\n";
  else
    cout << cautareBin << "\n";
}

int main()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> v[i];

  int m; cin >> m;
  for (int i = 1; i <= m; i++)
    {
      int tip, valoare;
      cin >> tip >> valoare;

      if (tip == 0)
	s1 (valoare);
      if (tip == 1)
	s2 (valoare);
      if (tip == 2)
	s3 (valoare);
    }

  return 0;
}