P9053 [PA 2021] Ranking of Online Stores

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}$.

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

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

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