Consider an array, $A=a_0,a_1,...,a_{n-1}$, of $n$ integers. We define the following terms:

Subsequence

A subsequence of $\mbox{A}$ is an array that's derived by removing zero or more elements from $\mbox{A}$ without changing the order of the remaining elements. Note that a subsequence may have zero elements, and this is called the empty subsequence.

Strictly Increasing Subsequence

A non-empty subsequence is strictly increasing if every element of the subsequence is larger than the previous element.

Subarray

A subarray of $\mbox{A}$ is an array consisting of a contiguous block of $\mbox{A}$'s elements in the inclusive range from index $\boldsymbol{l}$ to index $\textbf{r}$. Any subarray of $\mbox{A}$ can be denoted by $A[l,r]=a_l,a_{l+1},...,a_r$.

The diagram below shows all possible subsequences and subarrays of $A=[2,1,3]$:

We define the following functions:

$sum(l,r)=a_l+a_{l+1}+…+a_r$
$inc(l,r)$ = the maximum sum of some strictly increasing subsequence in subarray $A[l,r]$
$f(l,r)=sum(l,r)-inc(l,r)$

We define the goodness, $\mathrm{~g~}$, of array $\mbox{A}$ to be:

$g=max\ f(l,r)\ \text{for }\ 0\leq l\leq r\lt n$

In other words, $\mathrm{~g~}$ is the maximum possible value of $f(l,r)$ for all possible subarrays of array $\mbox{A}$.

Let $m$ be the length of the smallest subarray such that $f(l,r)=g$. Given $\mbox{A}$, find the value of $\mathrm{~g~}$ as well as the number of subarrays such that $r-l+1=m$ and $f(l,r)=g$, then print these respective answers as space-separated integers on a single line.

Input Format

The first line contains an integer, $n$, denoting number of elements in array $\mbox{A}$.

The second line contains $n$ space-separated integers describing the respective values of $a_0,a_1,\ldots,a_{n-1}$.

Constraints

$1\leq n\leq2\cdot10^5$
$-40\leq a_i\leq40$

Subtasks

For the $20\%$ of the maximum score:

$1\leq n\leq2000$

$-10\leq a_i\leq10$

For the $\textbf{60\%}$ of the maximum score:

$1\leq n\leq10^5$

$-12\leq a_i\leq12$

Output Format

Print two space-seperated integers describing the respective values of $\mathrm{~g~}$ and the number of subarrays satisfying $r-l+1=m$ and $f(l,r)=g$.

Sample Input 0
3
2 3 1

Sample Output 0
1 1

Explanation 0

The figure below shows how to calculate $\mathrm{~g~}$:

$m$ is the length of the smallest subarray satisfying $f(l,r)$. From the table, we can see that $m=2$. There is only one subarray of length $2$ such that $f(l,r)=g=1$.

见题面

见题面