#include<fstream>
using namespace std;
int n,t,v[100001],x,y;

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

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

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

int caut2 (int p, int u, int nr)
{
    int m;
    while (p < u)
    {
        m = (p + u) / 2;
        if (v[m] < nr)
            p = m + 1;
        else
            u = m;
    }
    m = (p + u) / 2;
    if (v[m] < nr) m++;
    return m+1;
}

int main()
{
    in>>n;
    for (int i=0; i<n; i++)
        in>>v[i];
    in>>t;
    for(int i = 1; i<=t; i++)
    {
        in>>x>>y;
        if(x==0)
        {
            out<<caut0(0,n-1,y)<<'\n';
        }
        else if(x==1)
        {
            out<<caut1(0,n-1,y)<<'\n';
        }
        else if(x==2)
        {
            out<<caut2(0,n-1,y)<<'\n';
        }
    }
    return 0;
}