#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100005];
//functie care cauta cea mai mare pozitie pe care se afla valoarea data
int cautare1(int primul,int ultimul,int valoare)
{
    int mijloc;
    while(primul<=ultimul)
    {
        mijloc=(primul+ultimul)/2;
        if(v[mijloc]==valoare)
        {
            while(v[mijloc]==valoare)
            {
                mijloc++;
            }
                return mijloc-1;
        }
        if(v[mijloc]<valoare)
        {
            primul=mijloc+1;
        }
        if(v[mijloc]>valoare)
        {
            ultimul=mijloc-1;
        }
    }
    //daca nu gasim valoarea data returnam -1
    return -1;
}

int cautare2(int primul,int ultimul,int valoare)
{
    int mijloc;
    while(primul<ultimul)
    {
        mijloc=(primul+ultimul)/2;
        if(v[mijloc]<=valoare)
        {
            primul=mijloc+1;
        }
        else
        {
            ultimul=mijloc;
        }
    }
    mijloc=(primul+ultimul)/2;
    //daca pozitia pe care suntem este mai mare decat valoarea data atunci scadem cu o pozitie
    if(v[mijloc]>valoare)
        mijloc--;

    return mijloc;
}
//prima pozitie pe care gasim valoarea data
int cautare3(int primul,int ultimul,int valoare)
{
    int mijloc;
    while(primul<ultimul)
    {
        mijloc=(primul+ultimul)/2;
        if(v[mijloc]<valoare)
        {
            primul=mijloc+1;
        }
        else
        {
            ultimul=mijloc;
        }
    }
    mijloc=(primul+ultimul)/2;
    //daca pozitia pe care suntem este mai mica decat valoarea data atunci crestem cu o pozitie
    if(v[mijloc]<valoare)
        mijloc++;

    return mijloc;
}
int main()
{
    int n,i,m,rezultat;
    fin>>n;

    for(i=1;i<=n;i++)
    {
        fin>>v[i];
    }

    //citim numarul de cerinte
    fin>>m;
    int varianta,valoare;
    while(m)
    {

        fin>>varianta>>valoare;
        fout<<m<<" ";
        if(varianta==0)
        {
            //fout<<"1";
            rezultat=cautare1(1,n,valoare);
            fout<<rezultat<<'\n';
        }
        if(varianta==1)
        {
            //fout<<"2";
            rezultat=cautare2(1,n,valoare);
            fout<<rezultat<<'\n';
        }
        if(varianta==2)
        {
            //fout<<"3";
            rezultat=cautare3(1,n,valoare);
            fout<<rezultat<<'\n';
        }
        m--;
    }
    return 0;
}