#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100005],n,m;
int Cbin(int x)
{ int l=1,r=n,mid;
  while(l<r)
  { mid=(l+r)/2;
    if (x>=a[mid]) l=mid+1; else r=mid-1;
  }
 mid=(l+r)/2;
 if (x<a[mid]) mid--;
 if (x==a[mid]) return mid;
 return -1;
}
int Cbin2(int x)
{ int l=1,r=n,mid;
  while(l<r)
  { mid=(l+r)/2;
    if (x>=a[mid]) l=mid+1; else r=mid-1;
  }
 mid=(l+r)/2;
 if (x<a[mid]) mid--;
 return mid;
}
int Cbin3(int x)
{ int l=1,r=n,mid;
  while(l<r)
  { mid=(l+r)/2;
    if (x>a[mid]) l=mid+1; else r=mid;
  }
 mid=(l+r)/2;
 if (x>a[mid]) mid++;
 return mid;
}
int main()
{ int i,tip,nr;
   f>>n;
   for(i=1;i<=n;i++) f>>a[i];
    f>>m;
    for(i=1;i<=m;i++)
    {f>>tip>>nr;
    if (tip==0) g<<Cbin(nr)<<"\n";
    if (tip==1) g<<Cbin2(nr)<<"\n";
    if (tip==2) g<<Cbin3(nr)<<"\n";
    }
    return 0;
}