// cautareBinara.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <fstream>
using namespace std;

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

int v[100001]; int n; int mijloc_vechi;

int cautareBinara (int el, int stanga, int dreapta)
{
  if (stanga > dreapta)
    return -1;

  int mijloc = (stanga + dreapta) / 2;

  if (el == v[mijloc])
    return mijloc;

  if (el > v[mijloc])
    return cautareBinara(el, mijloc + 1, dreapta);
  else
    return cautareBinara(el, stanga, mijloc - 1);
}

int cautareBinara2 (int el, int stanga, int dreapta)
{
  if (stanga > dreapta)
    return -1;

  if (stanga == n)
  {
	mijloc_vechi++;
	return -1;
  }

  int mijloc = (stanga + dreapta) / 2;

  if (el == v[mijloc])
    return mijloc;

  mijloc_vechi = mijloc;

  if (el > v[mijloc])
    return cautareBinara2(el, mijloc + 1, dreapta);
  else
    return cautareBinara2(el, stanga, mijloc - 1);

}

void elMaxim (int x)
{
	int poz = cautareBinara (x, 1, n);
	if (poz != -1)
	{
		while (v[poz] == x)
			poz++;
		cout << --poz << "\n";
	}
	else
		cout << -1 << "\n";
}

void elMediu (int x)
{
	int poz = cautareBinara2 (x, 1, n);

	if (poz == -1)
		cout << mijloc_vechi - 1 << "\n";
	else
		cout << poz << "\n";
}

void elMinim2 (int x)
{
	int poz = cautareBinara (x, 1, n);
	if (poz != -1)
	{
		while (v[poz] == x)
			poz--;
		cout << ++poz << "\n";
	}
	else
		cout << -1 << "\n";
}

void elMinim (int x)
{
	int poz = cautareBinara2(x, 1, n);
	if (poz != -1)
	{
		elMinim2 (x);
		return;
	}

	if (poz == -1)
	{
		cout << mijloc_vechi << "\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 type, nr;
      cin >> type >> nr;

      if (type == 0)
	    elMaxim (nr);
	  if (type == 1)
		elMediu (nr);
	  if (type == 2)
		elMinim (nr);
    }
}