#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)
{
  if (start > end)
    return -1;
  int mid = (start + end) / 2;
  if (v[mid] == x)
  {  
    while(v[mid+1] == x)
      mid++;
    return mid;
  }
  else
  {
    if(v[mid] > x)
      return bsearch1(start,mid-1,x);
    else
      return bsearch1(mid+1,end,x);
  }
  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;
}