#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;
        }
        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 nu gasim valoarea data returnam -1
    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)
        {
            return mijloc;
        }
        if(v[mijloc]<valoare)
        {
            primul=mijloc+1;
        }
        if(v[mijloc]>valoare)
        {
            ultimul=mijloc;
        }
    }

    //daca nu gasim valoarea data returnam -1
    return -1;
}
int main()
{
    int n,i,m,rezultat;
    fin>>n;

    for(i=0;i<n;i++)
    {
        fin>>v[i];
    }
    //citim numarul de cerinte
    fin>>m;
    int varianta,valoare;
    while(m)
    {

        fin>>varianta>>valoare;

        if(varianta==0)
        {
            rezultat=cautare1(0,n-1,valoare);
            cout<<rezultat<<'\n';
        }
        if(varianta==1)
        {
            rezultat=cautare2(0,n-1,valoare);
            cout<<rezultat<<'\n';
        }
        if(varianta==2)
        {
            rezultat=cautare3(0,n-1,valoare);
            cout<<rezultat<<'\n';
        }
        m--;
    }
    return 0;
}