#include <iostream>
#include <fstream>

using namespace std;

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

int n,i,v[100004],m;
int cb1(int l,int r,int y)
{
    int mij;

       while(l<=r)
       {
           mij=l+(r-l)/2;
           if(v[mij]==y)
           {
              if(v[mij+1]>y||mij==r)
              {
                  return mij;
              }
              else
              {
                  l=mij+1;
              }
           }
           else
           {
               if(v[mij]<y)
                l=mij+1;
               else
                r=mij-1;
           }
       }
       return -1;
}
int cb2(int l,int r,int y)
{
    int mij;
     while(l<=r)
        {
            mij=l+(r-l)/2;
            if(v[mij]<=y)
            {
                if(v[mij+1]>y||mij==r)
                {
                    return mij;
                }
                else
                    l=mij+1;
            }
            else
                r=mij-1;
        }
        return mij;
}

int cb3(int l,int r,int y)
{
    int mij;
     while(l<=r)
        {
            mij=l+(r-l)/2;
            if(v[mij]>=y)
            {
                if(mij==l||v[mij-1]<y)
                    return mij;
                else
                    r=mij-1;
            }
            else
                l=mij+1;
        }
        return mij;
}

int q,x;
int main()
{
     f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
    }
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>> q >> x;
        if(q==0)
            g<<cb1(1,n,x)<<"\n";
        if(q==1)
            g<<cb2(1,n,x)<<"\n";
        if(q==2)
            g<<cb3(1,n,x)<<"\n";

    }
    return 0;
}