#include <iostream>
#include <fstream>
#define MAX 100010

using namespace std;

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

int v[MAX];

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

int Caut1 (int st,int dr, int n)
{
    int m=0;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]<=n)
        st=m+1;
        else
        dr=m;
    }
    m=(st+dr)/2;
    if(v[m]>n)
    --m;
    return m;
}

int Caut2 (int st, int dr, int n)
{
    int m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[n]<n)
        st=m+1;
        else
        dr=m;

    }
    m=(st+dr)/2;
    if(v[m]<n)
    ++m;
    return m;
}

int main()
{int N,M,i,y,x;
f>>N;
for(i=1;i<=N;i++)
f>>v[i];
f>>M;
while(M!=0)
{M--;
    f>>y>>x;
    if(y==0)
    g<<Caut0(1,N,x)<<endl;
    if(y==1)
    g<<Caut1(1,N,x)<<endl;
    if(y==2)
    g<<Caut2(1,N,x)<<endl;
}

    return 0;
}