//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");

bool ok;

vector <int> x;
int n,i,m,j,a,b,low,up;
int main()
{
    cin>>n;
    x.resize(n+1);
    for (i=1;i<=n;++i) cin>>x[i];
    cin>>m;
    ok=false;
    for (j=1;j<=m;++j)
    {
        ok=false;
        up=0;
        low=0;
        cin>>a>>b;
        if (binary_search(x.begin()+1,x.end(),b)) ok=true;

        if (a==0)
        {
            if (ok)
            {
              up=upper_bound(x.begin()+1,x.end(),b) -x.begin();
              cout<<up-1<<"\n";
            }
            else cout<<"-1\n";
        }
        if (a==1)
        {
            //if (ok)
            //{
                up=upper_bound(x.begin()+1,x.end(),b) -x.begin();
                cout<<up-1<<"\n";
        }
        if (a==2)
        {
            low=lower_bound(x.begin()+1,x.end(),b)-x.begin();
            cout<<low<<"\n";
        }

    }
    return 0;
}