#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
unsigned n, m;
vector<unsigned> v;
vector<unsigned>::iterator x;

int main()
{
    unsigned aux,i,t;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>aux;
        v.push_back(aux);
    }
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>t>>aux;
        if(t==0)
        {
            if(!binary_search(v.begin(),v.end(),aux))g<<'-1\n';
            else
            {
                x=lower_bound(v.begin(),v.end(),aux+1);
                g<<x-v.begin()<<'\n';
            }
        }
        else if(t==1)
        {
            x=upper_bound(v.begin(),v.end(),aux);
            g<<x-v.begin()<<'\n';
        }
        else if(t==2)
        {
            x=lower_bound(v.begin(),v.end(),aux);
            g<<x-v.begin()<<'\n';
        }
    }
    return 0;
}