#include <fstream>

using namespace std;

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

int v[100001];

int ctbin (int val,int n,int cerinta)
{
  int pos=0,final1;
  for (int msk=1<<20;msk>0;msk=msk/2)
  {
    if (pos+msk<=n&&v[pos+msk]<=val)
        {
          pos=pos+msk;
          if (v[pos]<=val)
            final1=pos;
        }
  }
  if (cerinta==0)
  {
    if (v[pos]==val)
        return pos;
    else
        return -1;
  }
  if (cerinta==1)
    return final1;
}

int ctbin2 (int val,int n)
{
  int pos=0;
  for (int msk=1<<20;msk>0;msk=msk/2)
    if (pos+msk<=n&&v[pos+msk]<=val)
      pos=pos+msk;
    while (v[pos]==val)
        pos--;
    pos++;
      return pos;
}

int main()
{
    int n,i,m,nrprobl,x;
    in>>n;
    for (i=1;i<=n;i++)
      in>>v[i];
    in>>m;
    for (i=1;i<=m;i++)
    {
      in>>nrprobl>>x;
      if (nrprobl!=2)
      {
        out<<ctbin(x,n,nrprobl)<<'\n';
      }
      else
      {
        out<<ctbin2(x,n)<<'\n';
      }
    }
    return 0;
}