For each index $i$, find the maximum index k~(i \le k \le n) such that RMinQ(s_{i+1}, ..., s_k) > s_i. This can be done using binary search. Next, the desired index $j$ is defined as the position where the value RMaxQ(s_i, ..., s_k) is attained for i \le j \le k.

Thus, for each index $i$, we need to find the largest possible index $j$, and then, among all obtained pairs $(i,j)$, determine the maximum difference j - i.

Example

Consider the third example.

Let i = 2~(s_2 = 4). The largest index k = 7 satisfies the condition RMinQ(s_{i+1}, ..., s_k) > 4. The value of RMaxQ(s_3, ..., s_7) is attained at index j = 6.

Algorithm implementation

Let's declare the constants and arrays.

#define MAX 50010
#define LOGMAX 16
int dp_max[MAX][LOGMAX], dp_min[MAX][LOGMAX];
int a[MAX];

The function Build_RMQ_Array строит $RMQ$ таблицы для быстрых запросов минимума ($dp\_min$) и максимума ($dp\_max$):

• dp\_min[i][j] stores the minimum value over the segment of length 2^j starting at position $i$.

• dp\_max[i][j] stores the index of the element with the maximum value over the segment of length 2^j starting at $i$.

void Build_RMQ_Array(int *b)
{
  int i, j;
  for (i = 1; i <= n; i++) 
  {
    dp_min[i][0] = b[i];
    dp_max[i][0] = i;
  }

  for (j = 1; 1 << j <= n; j++)
    for (i = 1; i + (1 << j) - 1 <= n; i++)
    {
      if (b[dp_max[i][j - 1]] > b[dp_max[i + (1 << (j - 1))][j - 1]])
        dp_max[i][j] = dp_max[i][j - 1];
      else
        dp_max[i][j] = dp_max[i + (1 << (j - 1))][j - 1];

      dp_min[i][j] = 
        min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);
    }
}

The RangeMaxQuery function returns the index of the maximum element in the subsegment $[i,j]$.

int RangeMaxQuery(int i, int j)
{
  int k = 0;
  while ((1 << (k + 1)) <= j - i + 1) k++; 

  if (a[dp_max[i][k]] > a[dp_max[j - (1<<k) + 1][k]])
    return dp_max[i][k];
  else
    return dp_max[j - (1<<k) + 1][k];
}

The RangeMinQuery function returns the minimum value in the subsegment $[i,j]$.

int RangeMinQuery(int i, int j)
{
  int k = 0;
  while ((1 << (k + 1)) <= j - i + 1) k++; 
  return min(dp_min[i][k],dp_min[j - (1<<k) + 1][k]);
}

The BinSearch function uses binary search on the interval [Left; Right] to find the largest index $k$ such that all elements between Left + 1 and $k$ are greater than a[Left].

int BinSearch(int Left, int Right)
{
  int MinValue = a[Left++];
  if (RangeMinQuery(Left,Right) > MinValue) return Right;

  while (Right > Left)
  {
    int Middle = (Left + Right) / 2;
    if (RangeMinQuery(Left,Middle) > MinValue)
      Left = Middle + 1;
    else
      Right = Middle;
  }

  if (dp_min[Left][0] <= MinValue) Left--;
  return Left;
}

The main part of the program. Process the test cases sequentially.

while(scanf("%d",&n) == 1)
{
  for(i = 1; i <= n; i++) scanf("%d",&a[i]);

Build the $RMinQ$ and $RMaxQ$ arrays.

  Build_RMQ_Array(a);

For each index $i$:

• Using BinSearch(i, n), find the largest index $k$ such that all elements in the interval [i + 1; k] are greater than $a[i]$;

• In the interval $[i,k]$ find the index $j$ where the maximum value is reached.

• Check whether j - i is the largest difference.

  res = 0;
  for(i = 1; i <= n; i++)
  {
    k = BinSearch(i, n);
    j = RangeMaxQuery(i,k);
    if (j - i > res) res = j - i;
  }

Print the result. If res = 0, we should print $-1$.

  if (res == 0) res = -1;
  printf("%d\n",res);
}