/// Craciun Catalin
///  Cautbin
///   www.infoarena.ro/problema/cautbin
#include <fstream>
#include <iostream>

#define NMax 100005

using namespace std;

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

long V[NMax];
long n,m;

/*
long cautBin1(long el)
{
    long st=1, dr=n;

    while (st<=dr)
    {
        long m=(st+dr)/2;

        if (V[m]<=el)
            st=m+1;
        else
            dr=m-1;
    }

    long m=(st+dr)/2;

    if (V[m]>el)
        return m-1;
    else if (V[m]==el)
        return m;
    else
        return 0;
}

long cautBin2(long el)
{
    long st=1, dr=n;

    while (st<=dr)
    {
        long m=(st+dr)/2;

        if (V[m]<=el)
            st=m+1;
        else
            dr=m-1;
    }

    long m=(st+dr)/2;

    while (V[m]>el)
        m--;

    return m;
}

long cautBin3(long el)
{
    long st=1, dr=n;

    while (st<=dr)
    {
        long m=(st+dr)/2;

        if (V[m]<el)
            st=m+1;
        else
            dr=m-1;
    }

    long m=(st+dr)/2;

    while (V[m]<el)
        m++;

    return m;
}
*/

int cautBin1(int st, int dr, int x)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(V[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }

    m=(st+dr)/2;

    if(V[m]>x)
        m--;
    if(V[m]==x)
        return m;
    else
        return -1;
}

int cautBin2(int st, int dr, int x)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(V[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }

    while(V[m]>x)
        m--;
    return m;
}

int cautBin3(int st, int dr, int x)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(V[m]>=x)
            dr=m-1;
        else
            st=m+1;
    }

    m=(st+dr)/2;

    while(V[m]<x)
        m++;

    return m;
}

int main()
{
    f>>n;
    for (long i=1;i<=n;i++)
        f>>V[i];
    f>>m;
    for (long i=1;i<=m;i++)
    {
        long x,y;
        f>>x>>y;
        if (x==0)
            g<<cautBin1(0,n,y)<<'\n';
        else if (x==1)
            g<<cautBin2(0,n,y)<<'\n';
        else if (x==2)
            g<<cautBin3(0,n,y)<<'\n';
    }
    f.close();

    return 0;
}