#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 cauta0(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;
          if (v[st]==nr)
           return st;
           return -1;
      }

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

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

int cauta1(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)
     cauta1(m,dr,nr);//caut in dreapta
    else
     cauta1(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)
          g<<cauta0(1,n,el)<<'\n';

         if (tip==1)
          g<<cauta1(1,n,el)<<'\n';

         if (tip==2)
          g<<cauta2(1,n,el)<<'\n';
     }

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