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

    return 0;
}