题目描述

题目译自 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$ 构成一个排列。