#include<fstream>
using namespace std;

#define N 100010

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

int v[N];

int bsearch1(int start, int end, int x)
{
  int mid;
  while (start <= end)
  {
    mid = (start + end) / 2;
    if (v[mid] > x)
      end = mid - 1;
    else
      start = mid + 1;  
  }
  mid = (start + end) / 2;
  if (v[mid] > x) m--;
  if (v[mid] == x)
    return m;
  return -1;
}

int bsearch2(int start, int end, int x)
{
  int rez = bsearch1(start, end, x);
  if(rez == -1)
    return bsearch2(start, end, x-1);
  return rez;
}

int bsearch3(int start, int end, int x)
{
  int rez = bsearch1(start, end, x);
  if(rez == -1)
    return bsearch3(start, end, x+1);
  else
  {
    while(v[rez-1] == x)
      rez--;
  }
  return rez;
}


int main() 
{
  int n, m;
  f>>n;
  for (int i = 1 ; i <= n; i++)
    f>>v[i];
  f>>m;
  int a, b;
  for (int i = 1 ; i <= m; i++)
  {  
    f>>a>>b;
    if (a == 0)
      g<<bsearch1(1, n, b)<<endl;
    else if(a == 1)
      g<<bsearch2(1, n, b)<<endl;
    else
      g<<bsearch3(1, n, b)<<endl;
  } 
  return 0;
}