#include <iostream>
#include <fstream>
using namespace std;
ifstream  f("cautbin.in");
ofstream g("cautbin.out");
int v[100005], n, m, i, intrebare, x;

int cautbin0(int k)
{   int  mij, st=1, dr=n;
    while (st<=dr)
    {   mij=(st+dr)/2;
       if (v[mij]==k)
        {   if (v[mij+1]!=k) return mij;
            else st=mij+1;
        }
        else if (v[mij]<k) st=mij+1;
                else dr=mij-1;
    }
    return -1;
}
int cautbin1(int k)
{   int  mij, st=1, dr=n;
    while (st<=dr)
    {   mij=(st+dr)/2;
        if(v[mij]<=k && v[mij+1]<=k)
            st++;
        else  if (v[mij]<=k && v[mij+1]>k) return mij;
        if (v[mij]>k) dr=mij-1;
        else if(v[mij]<k) st=mij+1;
    }
    return dr;
}
int cautbin2(int k)
{   int  mij, st=1, dr=n;
    while (st<=dr)
    {   mij=(st+dr)/2;
        if(v[mij]>=k && v[mij-1]>=k)
            dr=mij-1;
        else  if (v[mij]>=k && v[mij-1]<k) return mij;
        if (v[mij]>k) dr=mij-1;
        else if (v[mij]<k) st=mij+1;
    }
    return st;
}
int main()
{   f>>n;
    for (i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for (i=1;i<=m;i++)
    {   f>>intrebare>>x;
        if(intrebare==0) g<<cautbin0(x)<<'\n';
        if(intrebare==1) g<<cautbin1(x)<<'\n';
        if(intrebare==2) g<<cautbin2(x)<<'\n';
    }
    return 0;
}