#include <iostream>
#include <fstream>

using namespace std;

ifstream q("cautbin.in");
ofstream w("cautbin.out");

int v[100010];

int cb0(int p, int n, int b)
{
    int m;
    while(p<=n)
    {
        m=(p+n)/2;
        if(v[m]<=b) p=m+1;
        else n=m-1;
    }
    m=(p+n)/2;
    if(v[m]>b) m--;
    if(v[m]==b) return m;
    return -1;
}

int cb1(int p, int n, int b)
{
    int m;
    while(p<=n)
    {
        m=(p+n)/2;
        if(v[m]<=b) p=m+1;
        else n=m-1;
    }
    m=(p+n)/2;
    if(v[m]>b) m--;
    return m;
}

int cb2(int p, int n, int b)
{
    int m;
    while(p<=n)
    {
        m=(p+n)/2;
        if(v[m]<b) p=m+1;
        else n=m-1;
    }
    m=(p+n)/2;
    if(v[m]<b) m++;
    return m;
}

int main()
{int n,m, i,a,b;
    q>>n;
    for(i=1;i<=n;i++) q>>v[i];
    q>>m;
    for(i=1;i<=m;i++)
    {
        q>>a>>b;
        if(a==0) w<<cb0(1,n,b)<<"\n";
        if(a==1) w<<cb1(1,n,b)<<"\n";
       if(a==2) w<<cb2(1,n,b)<<"\n";
    }

    return 0;
}