#include <iostream>
#include<fstream>
using namespace std;

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");
int v[100002],n,operatie,x,m;
int cautareBinara0(int st,int dr,int x)
{
    int ok=0,poz=-1;

    while (st<=dr and ok==0)
    {

        poz = (st+dr)/2;
        if(v[poz] == x)
            ok = 1;

        else if (v[poz] < x)
            st = poz+1;

        else
            dr = poz-1;


    }
    if (ok)
    {

        while(v[poz+1] == x)
            poz++;

        return poz;
    }

    else
        return -1;

}
int cautareBinara1(int st,int dr,int x)
{
    int ok=0,poz=-1;

    while (st<=dr and ok==0)
    {

        poz = (st+dr)/2;
        if(v[poz] == x)
            ok = 1;

        else if (v[poz] < x)
            st = poz+1;

        else
            dr = poz-1;


    }
    if (ok)
    {

        while(v[poz+1] == x)
            poz++;

        return poz;
    }

    else
    {

        if(v[poz]>x)
            poz--;
        return poz;
    }


}

int cautareBinara2(int st,int dr,int x)
{
    int ok=0,poz=-1;

    while (st<=dr and ok==0)
    {
        poz = (st+dr)/2;
        if(v[poz] == x)
            ok = 1;

        else if (v[poz] < x)
            st = poz+1;

        else
            dr = poz-1;

    }
    if (ok)
    {
        while(v[poz-1] == x)
            poz--;

        return poz;
    }

    else
    {
        if(v[poz]<x)
            poz++;
        return poz;
    }


}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>v[i];
    f>>m;
    for(int i=1; i<=m; i++)
    {
        f>>operatie>>x;
        if(operatie == 0)
            g<<cautareBinara0(1,n,x)<<"\n";
        if(operatie == 1)
            g<<cautareBinara1(1,n,x)<<"\n";
        if(operatie == 2)
            g<<cautareBinara2(1,n,x)<<"\n";
    }
    return 0;
}