#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int N,M,T,v[100010];

int CautareBinara(int x);
int CautareBinara1(int x);
int CautareBinara2(int x);

void rez(int q, int x)
{
    switch(q){
        case 0:
        {
            g<<CautareBinara(x)<<'\n';
            break;
        }
        case 1:
        {
            g<<CautareBinara1(x)<<'\n';
            break;
        }
        case 2:
        {
            g<<CautareBinara2(x)<<'\n';
            break;
        }
    }
}
int main()
{
    f>>N;
    for(int i=1;i<=N;i++)
    {
        f>>v[i];
    }
    f>>T;
    for(int i=1;i<=T;i++)
    {
        int q,x;
        f>>q>>x;
        rez(q,x);
    }
    return 0;
}


int CautareBinara(int x)
{
    int Sol = -1, Left = 0, Right = N;
    while(Left <= Right)
    {
        int Mid = (Left+Right) / 2;
        if(v[Mid] == x)
        {
            Sol = Mid;
            break;
        }
        if(v[Mid] > x)
            Right = Mid - 1;
        if(v[Mid] < x)
            Left = Mid + 1;
    }
    if(Sol!=-1)
    {
        while(v[Sol+1] == x)
        {
            Sol++;
        }
    }
    return Sol;
}
int CautareBinara1(int x)
{
    int r =CautareBinara(x);
    if(r != -1)
        return r;
    else{
        int Sol = -1, Left = 0, Right = N;
        while(Left <= Right)
        {
            int Mid = (Left+Right) / 2;
            if(v[Mid] > x)
            {
                Right = Mid - 1;

            }

            if(v[Mid] < x)
            {
                 Left = Mid + 1;
                 if(Left > Right)
                 return Sol;
            }

        }

    }

}
int CautareBinara2(int x)
{
    int Sol = -1, Left = 0, Right = N;
    while(Left <= Right)
    {
        int Mid = (Left+Right) / 2;
        if(v[Mid] == x)
        {
            Sol = Mid;
            break;
        }
        if(v[Mid] > x){
            Right = Mid - 1;
            if(Left > Right)
                return Mid;
        }
        if(v[Mid] < x){
            Left = Mid + 1;
        }
    }
    if(Sol != -1)
    {
        while(v[Sol-1] == x)
            Sol--;
        return Sol;
    }
}