#include <iostream>
#include <fstream>
#include <assert.h>

using namespace std;

#define dim 100010

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

long int a[dim];
long int n,m;
long int x;

void cit()
{
    fi>>n;

    for(long int i=1;i<=n;i++)
        fi>>a[i];

    fi>>m;
}

long int cb0()
{
    long int s,f,m;

    s=1;
    f=n;

    while(s<=f)
    {
        m=(s+f)/2;

        if(a[m]<=x)
            s=m+1;
        else
            f=m-1;
    }

    m=(s+f)/2;

    if(a[m]>x)
        m--;

    if(a[m]==x)
        return m;

    return -1;

}

long int cb1()
{
    long int s,f,m;

    s=1;
    f=n;

    while(s<f)
    {
        m=(s+f)/2;

        if(a[m]<=x)
            s=m+1;
        else
            f=m;
    }

    m=(s+f)/2;

    if(a[m]>x)
        m--;

    return m;
}

long int cb2()
{
    long int s,f,m;

    s=1;
    f=n;

    while(s<f)
    {
        m=(s+f)/2;

        if(a[m]<x)
            s=m+1;
        else
            f=m;
    }

    m=(s+f)/2;

    if(a[m]<x)
        m++;

    return m;
}

int main()
{
    cit();

    int t;

    for(long int i=1;i<=m;i++)
        {fi>>t>>x;
        switch(t)
            {case 0:
                {fo<<cb0();
                fo<<'\n';
                break;}
            case 1:
                {fo<<cb1();
                fo<<'\n';
                break;}
            case 2:
                {fo<<cb2();
                fo<<'\n';
                break;}
        }}

    return 0;
}