#include <iostream>
#include <fstream.h>
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

using namespace std;

#define N 100010
int a[N];

int check0(int val,int u)
{
    int p=1,m;
    while (p<=u)
    {
        m=(p+u)/2;
        if (a[m]<=val)
            p=m+1;
        else
            u=m-1;
    }

    if (a[m]>val)
        m--;
    if (a[m]==val)
        return m;
    else
        return -1;

}

int check1(int val,int u)
{
    int p=1,m;
    while (p<=u)
    {
        m=(p+u)/2;
        if (a[m]<=val)
            p=m+1;
        else
            u=m-1;
    }

    for (;a[m]>val;m--);
    return m;
}

int check2(int val,int u)
{
    int p=1,m;
    while (p<=u)
    {
        m=(p+u)/2;
        if (a[m]<=val)
            p=m+1;
        else
            u=m-1;
    }

    for (;a[m]>=val;m--);
    m++;
    return m;
}

int main()
{
    int m,n,tip,x;

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

    fin>>m;
    while(m--)
    {
        fin>>tip>>x;

        if (!tip)
            cout<<check0(x,n)<<endl;
        else if (tip==1)
            cout<<check1(x,n)<<endl;
        else
            cout<<check2(x,n);
    }
    return 0;
}