#include <fstream>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100000];
int f(int st,int dr,int x)
{
    int mij=(st+dr)/2;
    if(st<dr)
            {if(x==v[mij])
            return mij;
            if(x<v[mij])
            return (st,mij-1,x);
            else
            return (mij+1,dr,x);

            }
            if(dr<st)
            {
                mij=-1;
                return mij;
            }
}
int main()
{
    int st,dr,x,n,i,m,j,l,max=0,min=10000,mij=0,c;
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>v[i];
    }
    in>>m;
    for(j=1;j<=m;j++)
    {
        in>>l>>x;
        if(l==0)
        {
           mij=f(1,n,x);
           if(v[mij]==v[n/2])
           {
               while(v[mij]==v[n/2])
               {
                   mij++;
               }
                out<<mij-1<<endl;
           }
          else
          {
              out<<mij<<endl;
          }
        }
        if(l==1)
        {
            mij=f(1,n,x);
            while(mij==-1)
            {
                x=x-1;
            }
            if(v[mij]==v[n/2])
           {
               while(v[mij]==v[n/2])
               {
                   mij++;
               }
                out<<mij-1<<endl;
           }
          else
          {
              out<<mij<<endl;
          }
        }
        if(l==2)
        {
          mij=f(1,n,x);
            while(mij==-1)
            {
                x=x+1;
            }
            if(v[mij]==v[n/2])
           {
               while(v[mij]==v[n/2])
               {
                   mij--;
               }
                out<<mij+1<<endl;
           }
          else
          {
              out<<mij<<endl;
          }        }
    }
    return 0;
}