#include<iostream>
#include<fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N,M, x,i,y ,v[100001];

 int golan0(int st ,int dr, int x)
       {
           int mijl, p=-1;
           while(st<=dr)
           {
               mijl=(st+dr)/2;
               if(v[mijl]==x)
                  {
                     p=mijl;
                     st=mijl+1;
                    }
                    else if(x<v[mijl])dr=mijl-1;
                    else st=mijl+1;

           }
           return p;
       }

  int golan(int st ,int dr, int x)
       {
           int mijl, p=-1;
           while(st<=dr)
           {
               mijl=(st+dr)/2;
               if(v[mijl]<=x)
                  {
                     p=mijl;
                     st=mijl+1;
                    }
                    else dr=mijl-1;

           }
           return p;
       }

    int golan2(int st ,int dr, int x)
       {
           int mijl, p=-1;
           while(st<=dr)
           {
               mijl=(st+dr)/2;
               if(v[mijl]>=x)
                  {
                     p=mijl;
                     dr=mijl-1;
                    }
                    else st=mijl+1;

           }
           return p;
       }

int main()
{
    f>>N;
    for(i=1;i<=N; i++)
        f>>v[i];

     f>>M;
     for(i=1;i<=M ; i++)
     {
         f>>y>>x;
         if(y==0 )
         {
            g<<golan0(1,N,x)<<endl;;
          }
        if(y==1)
        {
            g<<golan(1,N,x)<<endl;
        }
        if(y==2)
        {
            g<<golan2(1,N,x)<<endl;
        }
     }

    f.close();
    g.close();
    return 0;

}