#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100005];
int cautbin0(int st,int dr,int val)
{
    int m;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (v[m] <= val)
            st = m + 1;
        else
            dr = m - 1;
    }
    m = (st + dr) / 2;

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

    m = (st + dr) / 2;
    if (v[m] > val)
       m--;
    return m;
}
int cautbin2(int st,int dr,int val)
{
    int m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]>=val)
           dr=m;
        else
            st=m+1;
    }
    m=(st+dr)/2;
    if(v[m]<val)
       m++;
    return m;
}
int main()
{
    int st,dr,mid,i,n,m,p,x;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>p>>x;
        if(p==0)
           fout<<cautbin0(1,n,x)<<"\n";
        if(p==1)
           fout<<cautbin1(1,n,x)<<"\n";
        if(p==2)
           fout<<cautbin2(1,n,x)<<"\n";
    }
    return 0;
}