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

const char infile[] = "cautbin.in";
const char outfile[] = "cautbin.out";
const unsigned int INF = 0x3f3f3f3f;


ifstream in(infile);
ofstream out(outfile);

int n, x[100000];


int binary0(int val)
{
  int st=1, dr = n,mid;
  while(st<dr)
  {
    mid = (st+dr)/2;
    if((x[mid] == val) && (x[mid+1]!=val))
      return mid;
    if(x[mid] > val)
      dr = mid;
    else st = mid+1;
  }
  if(x[st]==val)
    return st;

  return -1;
}

int binary1(int val)
{
  int st=1, dr = n,mid;
  while(st<dr)
  {
    mid = (st+dr)/2;
    if(x[mid] > val)
      dr = mid;
    else st = mid+1;
  }
  if(x[st]>val)
    --st;

  return st;
}

int binary2(int val)
{
  int st=1, dr = n,mid;
  while(st<dr)
  {
    mid = (st+dr)/2;
    if(x[mid] >= val)
      dr = mid;
    else st = mid+1;
  }
  if(x[mid] < val)
     ++mid;

  return mid;
}






int main()
{
  int nr,s,c,m;
  in>>n;
  for(int i=1;i<=n; ++i)
    in>>x[i];
  in>>m;
  while(m--)
  {
    in>>c>>nr;
    if(c==0)
      out<<binary0(nr)<<"\n";
    else if(c==1)
      out<<binary1(nr)<<"\n";
    else out<<binary2(nr)<<"\n";
  }


}