#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,i,x,p,r,v[100001];
int cautarebinara0(int s,int d,int c)
{
  int mij=(s+d)/2;
  if (s<=d)
  {
    if (v[mij]==c)
    {
      if (r<mij)
        r=mij;
      return cautarebinara0(mij+1,d,c);
    }
    else
    {
      if (c>v[mij])
      {
        return cautarebinara0(mij+1,d,c);
      }
      else
      {
        return cautarebinara0(s,mij-1,c);
      }
    }
  }
  else
  {
    if (r==0)
    {
      return -1;
    }
    else return r;
  }
}
int cautarebinara1(int s,int d,int c)
{
  int mij=(s+d)/2;
  if (s<=d)
  {
    if (v[mij]<=c)
    {
      if (r<mij)
        r=mij;
      return cautarebinara1(mij+1,d,c);
    }
    else
    {
      if (c>v[mij])
      {
        return cautarebinara1(mij+1,d,c);
      }
      else
      {
        return cautarebinara1(s,mij-1,c);
      }
    }
  }
  else
  {
    return r;
  }
}
int cautarebinara2(int s,int d, int c)
{
  int mij=(s+d)/2;
  if (s<=d)
  {
    if (v[mij]>=c)
    {
      if (r>mij)
        r=mij;
      return cautarebinara2(s,mij-1,c);
    }
    else
    {
      if (c>v[mij])
      {
        return cautarebinara2(mij+1,d,c);
      }
      else
      {
        return cautarebinara2(s,mij-1,c);
      }
    }
  }
  else
  {
    return r;
  }
}
int main ()
{
  f>>n;
  for (i=1;i<=n;i++)
    f>>v[i];
  f>>m;
  for (i=1;i<=m;i++)
  {
    f>>x>>p;
    if (x==0)
    {
      r=0;
      g<<cautarebinara0(1,n,p)<<'\n';
    }
    else
    {
      if (x==1)
      {
        r=0;
        g<<cautarebinara1(1,n,p)<<'\n';
      }
      else
      {
        r=n;
        g<<cautarebinara2(1,n,p)<<'\n';
      }
    }
  }
}