#include <bits/stdc++.h>
#define zeros(x) ((x ^ (x - 1)) & x)
#define oo 0x3f3f3f3f

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[1000001], n, m, x, y;

void read()
{
  f>>n;
  for(int i = 1;i <= n;++i)
    f>>a[i];
}

int solve_1(int val)
{
  int left = 1, right = n, rez = -1, mid;
  while(left <= right)
  {
    mid = (left + right) >> 1;
    if(a[mid] == val)
      rez = mid, left = mid + 1;
    else if(a[mid] < val)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return rez;
}

int solve_2(int val)
{
  int left = 1, right = n, rez = -1, mid;
  while(left <= right)
  {
    mid = (left + right) >> 1;
    if(a[mid] <= val)
      rez = mid, left = mid + 1;
    else
      right = mid - 1;
  }
  return rez;
}

int solve_3(int val)
{
  int left = 1, right = n, rez = -1, mid;
  while(left <= right)
  {
    mid = (left + right) >> 1;
    if(a[mid] >= val)
      rez = mid, right = mid - 1;
    else
      left = mid + 1;
  }
  return rez;
}

void solve()
{
  f>>m;
  for(int i = 1;i <= m;++i)
    {
      f>>x>>y;
      if(!x)
        g<<solve_1(y)<<'\n';
      else if(x == 1)
        g<<solve_2(y)<<'\n';
      else
        g<<solve_3(y)<<'\n';
    }
}

int main()
{
  read();
  solve();
  return 0;
}