#include <stdio.h>
int v[100005],n,m,y,x;
int caut0(int p, int q,int x)
{ int m;
   if(q>p)
    { m=(p+q)/2;
      if(v[m]==x)
      {while(v[m]==x)
       m=m+1;
       return m-1;}

        if(x>v[m])
         return caut0(m+1,q,x);
        else
         return caut0(p,m,x);
    }
    return -1;

}

int caut1(int p, int q,int x)
{ int m;
   if(q>p)
    { m=(p+q)/2;
      if(v[m]<=x)
      {while(v[m]<=x)
       m=m+1;
       return m-1;}

        if(x>v[m])
         return caut0(m+1,q,x);
        else
         return caut0(p,m,x);
    }


}

int caut2(int p, int q,int x)
{ int m;
   if(q>p)
    { m=(p+q)/2;
      if(v[m]>=x)
      {while(v[m]>=x)
          m=m-1;
       return m+1;}

        if(x>v[m])
         return caut2(m+1,q,x);
        else
         return caut2(p,m,x);
    }


}


int main()
{  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=1;i<=m;++i)
    {
      scanf("%d%d", &x,&y);
       switch(x)
     {
      case 0: {printf("%d\n",caut0(1,n,y)); break;}
      case 1: {printf("%d\n",caut1(1,n,y)); break;}
      case 2: {printf("%d\n",caut2(1,n,y)); break;}
     }
 }
   return 0;

}