#include <fstream>

using namespace std;

int v[100001];

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

int cautare (int x,int n,int cer)
{
  int pos=0,last;
  for (int msk=1<<20; msk; msk/=2)
    if (pos+msk<=n&&v[pos+msk]<=x)
        {
          pos+=msk;
          if (v[pos]<=x)
                last=pos;
        }
  if (cer==0)
  {
    if (v[pos]==x)
        return pos;
    return -1;
  }
  else if (cer==1)
    {return last;}
  while (v[pos]==x)
    pos--;
  pos++;
  return pos;
}

int main()
{
    int n,m,a,b;
    in>>n;
    for (int i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for (int i=1;i<=m;i++)
    {
      in>>a>>b;
      out<<cautare(b,n,a)<<'\n';
    }
    return 0;
}