#include <fstream>

#include <iostream>

using namespace std;

int v[100001];
int n, m;

ifstream in ("cautbin.in");
ofstream out ("cautbin.out");

int cautbin0 (int x)
{
    int inceput=1, sfarsit=n, mijloc = inceput/2 + sfarsit/2, pozitie;
    if(x<v[inceput]||x>v[sfarsit])
        return -1;
    while(x!=v[inceput]&&x!=v[sfarsit]&&x!=v[mijloc])
    {
        if(x<v[mijloc])
        {
            sfarsit=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        else
        {
            inceput=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        if(x==v[inceput])
            pozitie=inceput;
        if(x==v[mijloc])
            pozitie=mijloc;
        if(x==v[sfarsit])
            pozitie=sfarsit;
    }
    if(x==v[inceput])
        pozitie=inceput;
    if(x==v[mijloc])
        pozitie=mijloc;
    if(x==v[sfarsit])
        pozitie=sfarsit;
    pozitie++;
    while(x==v[pozitie])
        pozitie++;
    pozitie--;
    return pozitie;
}

int cautbin1 (int x)
{
    int inceput=1, sfarsit=n, mijloc = inceput/2 + sfarsit/2, pozitie;
    while(x>v[inceput]&&x>v[sfarsit]&&x>v[mijloc])
    {
        if(x<v[mijloc])
        {
            sfarsit=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        else
        {
            inceput=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        if(v[inceput]<=x)
            pozitie=inceput;
        if(v[mijloc]<=x)
            pozitie=mijloc;
        if(v[sfarsit]<=x)
            pozitie=sfarsit;
    }
    if(v[inceput]<=x)
            pozitie=inceput;
    if(v[mijloc]<=x)
            pozitie=mijloc;
    if(v[sfarsit]<=x)
            pozitie=sfarsit;
    pozitie++;
    while(v[pozitie]<=x)
        pozitie++;
    pozitie--;
    return pozitie;
}

int cautbin2 (int x)
{
    int inceput=1, sfarsit=n, mijloc = inceput/2 + sfarsit/2, pozitie;
    while(x<v[inceput]&&x<v[sfarsit]&&x<v[mijloc])
    {
        if(x<v[mijloc])
        {
            sfarsit=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        else
        {
            inceput=mijloc;
            mijloc=inceput/2 + sfarsit/2;
        }
        if(v[inceput]>=x)
            pozitie=inceput;
        if(v[mijloc]>=x)
            pozitie=mijloc;
        if(v[sfarsit]>=x)
            pozitie=sfarsit;
    }
    if(v[inceput]>=x)
            pozitie=inceput;
    if(v[mijloc]>=x)
            pozitie=mijloc;
    if(v[sfarsit]>=x)
            pozitie=sfarsit;
    pozitie--;
    while(v[pozitie]>=x)
        pozitie--;
    pozitie++;
    return pozitie;
}

int main()
{
    in>>n;
    int i, tip, numar;
    for(i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>tip>>numar;
        if(tip==0)
            out<<cautbin0(numar)<<"\n";
        if(tip==1)
            out<<cautbin1(numar)<<"\n";
        if(tip==2)
            out<<cautbin2(numar)<<"\n";

    }
    return 0;
}