#include <fstream>
using namespace std;

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

int v[100005] , n;
int cb1(int x)
{
int st=1,dr=n;
while (st <= dr)
{
	int mid = (st + dr) / 2;
	if (v[mid] < x)
		st = mid + 1;
	else
		dr  = mid - 1;
}
return st;
}//returneaza cel mai mic nr >= x
int cb2(int x)
{
int st=1,dr=n;
while (st <= dr)
{
	int mid = (st + dr) / 2;
	if (v[mid] <= x)
		st = mid + 1;
	else
		dr  = mid - 1;
}
return st;
}//returneaza cel mai mic nr > x

int cb3(int x)
{
int st=1,dr=n;
while (st <= dr)
{
	int mid = (st + dr) / 2;
	if (v[mid] < x)
		st = mid + 1;
	else
		dr  = mid - 1;
}
return st;
}//returneaza cel mai mare nr <= x;

int cb4(int x)
{
int st=1,dr=n;
while (st <= dr)
{
	int mid = (st + dr) / 2;
	if (v[mid] >= x)
		st = mid + 1;
	else
		dr  = mid - 1;
}
return st;
}//cel mai mare nr < x;
int lowerBound(int target)
{
     int l = 1,h = n + 1;
  while(l < h)
  {
      int mid = (l + h) / 2;
      if(v[mid] >= target)
        h = mid;
      else l = mid + 1;
  }
  return h;
}
int upperBound(int target)
{
    int l = 1,h = n + 1;
  while(l < h)
  {
      int mid = (l + h) / 2;
      if(v[mid] > target)
        h = mid;
      else l = mid + 1;
  }
  return h;
}


int main()
{
    int x, m, q;
    in >> n;
    for(int i = 1;i <= n;i ++)
        in >> v[i];
    in >> m;
    for(int i = 0;i < m;i ++)
    {
        in >> q >> x;
        if(q == 0)
        {
            if(v[cb2(x) - 1] == x)out<<cb2(x) - 1;
            else out <<-1;
        }
        else if(q == 1)
        {
           out << upperBound(x) - 1;
        }
        else if(q == 2)
        {
            out << lowerBound(x);
        }
        out <<"\n";
    }

    return 0;
}