#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,i,t,nr,a[100010],x;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++) fin>>a[i];
    fin>>t;
    while(t--)
    {
      fin>>nr>>x;
      if(!nr)
      {
        if(!binary_search(a+1,a+n+1,x)) fout<<"-1"<<"\n"; 
		else
        fout<<upper_bound(a+1,a+n+1,x)-a-1<<"\n";
      }
      if(nr==1) fout<<upper_bound(a+1,a+n+1,x)-a-1<<"\n";
      if(nr==2) fout<<lower_bound(a+1,a+n+1,x)-a<<"\n";
    }

    return 0;
}