#include <cstdio>

using namespace std;

int v[100073];

int cautbin1(int val,int ls, int ld)
{
    int mij,sol=-1;
    mij=(ls+ld)/2;
    while (ls<=ld)
   {
    if (v[mij]==val)
        sol=mij;
    if (v[mij]<=val)
        ls=mij+1;
    else ld=mij-1;
        mij=(ls+ld)/2;

   }

    return sol;
}

int cautbin2(int val, int ls, int ld)
{
    int mij,sol;
    mij=(ld+ls)/2;
    while (ls<=ld)
    {
        if (v[mij]<=val)
       {
         sol=mij;
         ls=mij+1;
       }
       else ld=mij-1;
        mij=(ld+ls)/2;


    }
return sol;
}

int cautbin3(int val,int ls, int ld)
{
   int mij,sol;
   mij=(ls+ld)/2;

   while (ls<=ld)
   {
       if (v[mij]>=val)
       {
           sol=mij;
           ld=mij-1;
       }
        else ls=mij+1;
        mij=(ls+ld)/2;

   }
   return sol;
}

int main()
{
    int m,n,op,x;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    scanf("%d",&n);

    for (int i=1;i<=n;i++)
        scanf("%d",&v[i]);

    scanf("%d",&m);

    for (int i=0;i<m;i++)
        {
            scanf("%d%d",&op,&x);
            if (op==0) printf("%d\n",cautbin1(x,1,n));
            else if (op==1) printf("%d\n", cautbin2(x,1,n));
            else printf("%d\n",cautbin3(x,1,n));
        }
    return 0;
}