题目描述

给定长为 $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$。

输出格式

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

5
1 4 3 5 2

11 5

提示

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