/*
    Keep It Simple!
*/

#include<stdio.h>

int n,v[100005],x;

int Binary1(int x)
{
    int left = 1, right = n;

    while(left<right-1)
    {
        int mid = (left+right)/2;
        if( x == v[right])
          return right;
        if( v[mid] <= x)
         left = mid;
        else
         right = mid - 1;
    }
    if(v[right] == x)
      return right;
    else if (v[left] == x)
      return left;
    else
    return -1;
}

int Binary2(int x)
{
   int left = 1, right = n;

    while(left<right-1)
    {
        int mid = (left+right)/2;
        if( v[mid] <= x)
         left = mid;
        else
         right = mid - 1;
    }
    if(v[right] <= x)
      return right;
    else if (v[left] <= x)
      return left;
}

int Binary3(int x)
{
   int left = 1, right = n;

    while(left<right-1)
    {
        int mid = (left+right)/2;
        if( v[mid] >= x)
         right = mid-1;
        else
         left = mid;
    }
    if (v[left] >= x)
      return left;
    if(v[right] >= x)
      return right;

}

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]);

   int T,type;

   scanf("%d",&T);

   for(int i=1;i<=T;i++)
   {
      scanf("%d%d",&type,&x);
      if( type == 0 )
        printf("%d\n",Binary1(x));
      else if(type == 1)
        printf("%d\n",Binary2(x));
      else if(type == 2)
        printf("%d\n",Binary3(x));
   }

}