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

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

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

void 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)
    {
      out << m << '\n';
    }
    else  if(v[m] != val)
    {
      out << -1 << '\n';
    }
}

void 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)
    {
      out << m << '\n';
    }
}

void 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)
    {
      out << m << '\n';
    }
}

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)
    {
      cautbin0(1,n,val); 
    }
    if(q == 1)
    {
      cautbin1(1,n,val);
    }
    if(q == 2)
    {
      cautbin2(1,n,3);
    }
  }
  return 0;
}