题目描述
题目译自 $PA$ $2021$ $Runda$ $4$ $Ranking$ $sklepów$ $internetowych$

给定长度为 $n$ 的 $1 \sim n$ 排列 $\{a_i\}$。

定义区间 $[l, r]$ 的权值如下：将区间内的数从小到大排序，设 $X = r - l + 1$，$Y = a_{\lceil n/2 \rceil}+a_{\lceil (n+1)/2 \rceil}$，区间的权值为 $X + Y$。

求出 $\frac{n(n+1)}{2}$ 个区间中，权值的最大值以及最大值个数。

输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数 $a_i$。

输出格式
输出 $\frac{n(n+1)}{2}$ 个区间中，权值的最大值以及最大值个数。

样例
输入

5
1 4 3 5 2

输出

11 5

数据范围与提示
$1 \leq n \leq 10^6$
$1 \leq a_i \leq n$
保证 $a_i$ 构成一个排列。