#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,int dr)
{
    int m;
    if (st<=dr)
    {
        m=(st+dr)/2;
        if (s[m]<=x)
            return binar0(m+1,dr);
        else
            return binar0(st,m-1);
    }
    m=(st+dr)/2;
    if (s[m]>x)
        --m;
    if (s[m]==x)
        return m;
    return (-1);
}
int binar1(int st,int dr)
{
    int m;
    if (st<dr)
    {
        m=(st+dr)/2;
        if (s[m]<=x)
            return binar1(m+1,dr);
        else
            return binar1(st,m);
    }
    m=(st+dr)/2;
    if (s[m]>x)
        --m;
    return m;
}
int binar2(int st,int dr)
{
    int m;
    while (st<dr)
    {
        m=(st+dr)/2;
        if (s[m]<x)
            return binar2(m+1,dr);
        else
            return binar2(st,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(1,n);
        if (y==1) fo<<binar1(1,n);
        if (y==2) fo<<binar2(1,n);
        fo<<"\n";
    }
    fo.close();
}