#include <iostream>
#include <fstream>
using namespace std;

ifstream in("leftmax.in");
ofstream out("leftmax.out");

const int N = 100005;
int v[N];

int cautbin0(int l, int r, int val)
{
    int m;
    while (l <= r) {
        m = (l + r) / 2;
        if (v[m] <= val)
            l = m + 1;
        if (v[m] > val)
            r = m - 1;
    }
    m = (l + r) / 2;
    if(v[m] > val) m--;
    if(v[m] == val)
    {
      return m;
    }
    return -1;
}

int cautbin1(int l, int r, int val)
{
   int m;
    while (l <= r) {
        m = (l + r) / 2;
        if (v[m] <= val)
            l = m + 1;
        if (v[m] > val)
            r = m - 1;
    }
    m = (l + r) / 2;
    if(v[m] > val) m--;
    if(v[m] <= val)
    {
      return m;
    }
}

int cautbin2(int l, int r, int val)
{
   int m;
    while (l <= r) {
        m = (l + r) / 2;
        if (v[m] < val)
            l = m + 1;
        if (v[m] >= val)
            r = m - 1;
    }
    m = (l + r) / 2;
    if(v[m] < val) m++;
    if(v[m] >= val)
    {
      return m;
    }
}
int main()
{
  int n, m;
  int q,val;
  in >>  n;
  for (int i = 1; i <= n; i++)
  {
    in >> v[i];
  }
  in >> m;
  for(int i = 1; i <= m; i++)
  {
    in >> q >> val;
    if(q == 0)
    {
      out << cautbin0(1,n,val) << '\n';
    }
    if(q == 1)
    {
      out << cautbin1(1,n,val) << '\n';
    }
    if(q == 2)
    {
       out << cautbin2(1,n,3) << '\n';
    }
  }
  return 0;
}