#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,v[100001],m,x,y;
int x1 (int val)
{
    int st=0,sf=n,lm;
    while (st<=sf)
    {
        lm=(st+sf)/2;
        if (v[lm]>val)
        {
            sf=lm-1;
        }
        else
        {
            st=lm+1;
        }
    }
    if (v[lm]!=val)
        lm--;
    if (v[lm]==val)
        return lm;
    else return -1;
}
int x2 (int val)
{
    int st=0,sf=n,lm;
    while (st<=sf)
    {
        lm=(st+sf)/2;
        if (v[lm]>val)
            sf=lm-1;
        else st=lm+1;
    }
  //  lm=(st+sf)/2;
    return lm;
}
int x3 (int val)
{
    int st=0,sf=n,lm;
    while (st<=sf)
    {
        lm=(st+sf)/2;
        if (v[lm]>=val)
            sf=lm-1;
        else st=lm+1;
    }
    //lm=(st+sf)/2;
    return lm;
}
int main()
{
    f>>n;
    for (int i=0; i<n; i++)
    {
        f>>v[i];
    }
    f>>m;
    for (int i=0; i<m; i++)
    {
        f>>x>>y;
        if (x==0)
        {
            g<<x1(y)+1<<'\n';
        }
        else if (x==1)
        {
            g<<x2(y)+1<<'\n';
        }
        else
        {
            g<<x3(y)+1<<'\n';
        }
    }
    return 0;
}