#include <fstream>
#define lmax 100000

using namespace std;

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

int n,m,tip,el,i;
int v[lmax];

int cauta01(int st,int dr,int nr)
{
    int m=(st+dr)/2;

    if (st==dr && v[st]<=nr)
     return dr;
    else
     if (st==dr-1)
      if (v[dr]<=nr)
       return dr;
      else
       return st;

    if (st==dr && v[st]>nr)//nu gasesc elem
     return -1;

    if (v[m]<=nr)
     cauta01(m,dr,nr);//caut in dreapta
    else
     cauta01(st,m,nr);//caut in stanga
}

int cauta2(int st,int dr,int nr)
{
    int m=(st+dr)/2;

    if (st==dr && v[st]<=nr)
     return dr;
    else
     if (st==dr-1)
      if (v[st]>=nr)
       return st;
      else
       return dr;

    if (st==dr && v[st]<nr)//nu gasesc elem
     return -1;

    if (v[m]<nr)
     cauta2(m,dr,nr);//caut in dreapta
    else
     cauta2(st,m,nr);//caut in stanga
}

int main()
{
    f>>n;

    for (i=1;i<=n;i++)
     f>>v[i];

    f>>m;

    for (i=1;i<=m;i++)
     {
         f>>tip>>el;
         if (tip==0 || tip==1)
          g<<cauta01(1,n,el)<<'\n';
         else
          g<<cauta2(1,n,el)<<'\n';
     }

   f.close();
   g.close();
}