Goodness of a sequence

You are given a sequence $A = A_0, A_1, \dots, A_{N-1}$ of $N$ integers. Subsequences, increasing subsequences, and contiguous subsequences are defined as follows.

• Subsequence: a sequence built by deleting zero or more numbers from $A$. The numbers that are kept stay in their original order. A subsequence may have size $0$, and that one is called the empty subsequence.
• Increasing subsequence: a subsequence of length at least $1$ in which every number is larger than the number right before it.
• Contiguous subsequence: a subsequence whose kept numbers are neighbors in the original sequence $A$. The contiguous subsequence made of the $l$-th through the $r$-th numbers of $A$ is written $A[l, r] = A_l, A_{l+1}, \dots, A_r$. ($l \le r$)

For $A = [2, 1, 3]$, the subsequences are $[], [2], [1], [3], [2, 1], [2, 3], [1, 3], [2, 1, 3]$, the contiguous subsequences are $[2], [1], [3], [2, 1], [1, 3], [2, 1, 3]$, and the increasing subsequences are $[2], [1], [3], [2, 3], [1, 3]$.

Three functions are defined on a sequence.

• $sum(l, r) = A_l + A_{l+1} + \dots + A_r$
• $inc(l, r)$: the largest sum of the elements of an increasing subsequence of $A[l, r]$
• $f(l, r) = sum(l, r) - inc(l, r)$

The goodness $g$ of the sequence is $g = \max f(l, r)$ over $0 \le l \le r < N$. That is, $g$ is the largest $f(l, r)$ among all contiguous subsequences of $A$.

Let the integer $m$ be the smallest length of a contiguous subsequence with $f(l, r) = g$.

Given $A$, find $g$ first, then count the contiguous subsequences with $r - l + 1 = m$ and $f(l, r) = g$.

The first line contains an integer $N$ ($1 \le N \le 200{,}000$). The second line contains $A_0, A_1, \dots, A_{N-1}$ separated by spaces. ($-40 \le A_i \le 40$)

Print two integers on one line, separated by a space. The first integer is $g$ for the given sequence. The second integer is the number of contiguous subsequences with $r - l + 1 = m$ and $f(l, r) = g$.