#include <fstream>
#include <iostream>
using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
const int nmax=100001;
int s[nmax],n,x;
int binar0()
{
    int st=1,dr=n,m;
    while (st<=dr)
    {
        m=(st+dr)/2;
        if (s[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }
    m=(st+dr)/2;
    if (s[m]>x)
        --m;
    if (s[m]==x)
        return m;
    return (-1);
}
int binar1()
{
    int st=1,dr=n,m;
    while (st<dr)
    {
        m=(st+dr)/2;
        if (s[m]<=x)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if (s[m]>x)
        --m;
    return m;
}
int binar2()
{
    int st=1,dr=n,m;
    while (st<dr)
    {
        m=(st+dr)/2;
        if (s[m]<x)
            st=m+1;
        else
              dr=m;
    }
    m=(st+dr)/2;
    if (s[m]<x)
        ++m;
    return m;
}
int main(void)
{
    fi>>n;
    for (int i=1;i<=n;++i)
        fi>>s[i];
    int m;
    int y;
    for (fi>>m;m;--m)
    {
        fi>>y>>x;
        if (!y)   fo<<binar0();
        if (y==1) fo<<binar1();
        if (y==2) fo<<binar2();
        fo<<"\n";
    }
    fo.close();
}