#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
int n,m,i,nr,x,a[100000],up,low,bin;
int main()
{ fi>>n;
  for (i=1;i<=n;i++) fi>>a[i];
  fi>>m;

for(i=1;i<=m;i++)
  {fi>>nr>>x;
  bin=binary_search(a+1,a+n+1,x);
  up=upper_bound(a+1,a+n+1,x)-a-1;
  low=lower_bound(a+1,a+n+1,x)-a;

if (nr==0) if (bin) fo<<up<<"\n"; else fo<<"-1"<<"\n";
if (nr==1) fo<<up<<"\n";
if (nr==2) fo<<low<<"\n";

  }

    return 0;
}