P9053 [PA 2021] Ranking sklepów internetowych

给定长为 $n$ 的**排列** $a$。 定义区间 $[l, r]$ 的权值如下：将区间内的数从小到大排序，设 $x$ 为区间长度（即 $r - l + 1$），$y$ 为区间中位数，则该区间的权值为 $x + 2y$。 求所有 $\frac{n(n + 1)}{2}$ 个区间中权值的最大值和最大值的个数。 ------------ 中位数的定义： 以一个长为 $n$ 的**单调递增**的序列 $a$ 为例。 - 当 $n$ 为奇数，中位数为 $a_{\frac{n + 1}{2}}$。 - 当 $n$ 为偶数，中位数为 $\frac{a_{\frac{n}{2}} + a_{\frac{n}{2} + 1}}{2}$。

第一行，一个整数 $n$； 第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$。

一行，两个整数，表示权值的最大值和最大值的个数。

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq a_i \leq n$。