Problem Description

You are given a permutation $a$ of length $n$.

Define the weight of an interval $[l, r]$ as follows: sort the numbers in the interval in increasing order. Let $x$ be the interval length (that is, $r - l + 1$), and let $y$ be the median of the interval. Then the weight of this interval is $x + 2y$.

Among all $\frac{n(n + 1)}{2}$ intervals, find the maximum weight and the number of intervals whose weight equals this maximum.

Definition of the median:

Take a strictly increasing sequence $a$ of length $n$ as an example.

• If $n$ is odd, the median is $a_{\frac{n + 1}{2}}$.
• If $n$ is even, the median is $\frac{a_{\frac{n}{2}} + a_{\frac{n}{2} + 1}}{2}$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

Output one line with two integers: the maximum weight and the number of intervals that achieve this maximum weight.

5
1 4 3 5 2

11 5

Hint

For $100\%$ of the testdata, $1 \leq n \leq 10^6$, $1 \leq a_i \leq n$.

Translated by ChatGPT 5