#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int v[100001];

//3 functii de cautare corespunztoare tipului de intrebare:

int cautare0(int st, int dr, int x)
{
    if (st>dr)
        return -1;
    int k = (st+dr)/2;
    if (v[k] == x && v[k+1] > x)
        return k;
    else
    {
        if (v[k] <= x)
            return cautare0(k+1,dr,x);
        else
            return cautare0(st,k-1,x);
    }
}

int cautare1(int st, int dr, int x)
{
    if (st>dr)
        return -1;
    int k = (st+dr)/2;
    if (v[k]<=x && v[k+1]>x)
        return k;
    else
    {
        if (v[k] <= x)
            return cautare1(k+1,dr,x);
        else
            return cautare1(st,k-1,x);
    }
}

int cautare2(int st, int dr, int x)
{
    if (st>dr)
        return -1;
    int k = (st+dr)/2;
    if (v[k]>=x && v[k-1]<x)
        return k;
    else
    {
        if (v[k]>=x)
            return cautare2(st,k-1,x);
        else
            return cautare2(k+1,dr,x);
    }
}

int main()
{
    //citire:
    int n;
    in >> n;
    int i;
    for (i=1; i<=n; i++)
        in >> v[i];

    //rezolvare intrebari:
    int m;
    in >> m;
    int tipIntrebare, elementCautat;
    for (i=1; i<=m; i++)
    {
        in >> tipIntrebare >> elementCautat;
        if (tipIntrebare == 0)
            out << cautare0(1,n,elementCautat) <<"\n";
        else
        {
            if (tipIntrebare == 1)
                out << cautare1(1,n,elementCautat) <<"\n";
            else
                out << cautare2(1,n,elementCautat) <<"\n";
        }
    }


    return 0;
}