#include <iostream>
#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int *v,n,m;
void (*fc[3])(int);

void cautbin0(int x)
{
    int a,b,m;
    a=1;
    b=n;
    while (a<=b)
    {
        m=(a+b)/2;
        if (v[m]<=x) a=m+1;
        else b=m-1;
    }
    if (v[m]>x) m--;
    if (v[m]==x) g<<m;
    else g<<-1;
}

void cautbin1(int x)
{
    int a,b,m;
    a=1;
    b=n;
    while (a<=b)
    {
        m=(a+b)/2;
        if (v[m]<=x) a=m+1;
        else b=m-1;
    }
    if (v[m]>x) g<<m-1;
    else g<<m;
}

void cautbin2(int x)
{
    int a,b,m;
    a=1;
    b=n;
    while (a<=b)
    {
        m=(a+b)/2;
        if (v[m]>=x) b=m-1;
        else a=m+1;
    }
    if (v[m]<x) g<<m+1;
    else g<<m;
}

int main()
{
    int i,caz,val;
    fc[0]=cautbin0;
    fc[1]=cautbin1;
    fc[2]=cautbin2;

    f>>n;
    v=new int[n+1];
    for (i=1; i<=n; i++)
        f>>v[i];
    f>>m;
    for (i=1; i<m; i++)
    {
        f>>caz>>val;
        fc[caz](val);
        g<<'\n';
    }
    f>>caz>>val;
    fc[caz](val);
    f.close();
    g.close();
    return 0;
}