Bajtek 经营着一家网店。他的客户通常非常满意，并在网上给出非常积极的评价。然而，不幸的是，有时会有人出于某种原因给出虚假且负面的评价。也许那个人心情不好，也许他把 Bajtek 的店和另一家类似的店搞混了，又或者是因为 Bajtek 拒绝以低价出售商品而对他心怀不满？

在 Bajtek 关注的网店排名中，每个用户都可以给商店打一个整数分。Bajtek 的商店已经收到了 $n$ 个评分：$a_1, a_2, \dots, a_n$。这些评分按其给出的时间顺序排列，从最早到最晚。有趣的是，从 $1$ 到 $n$ 的每个评分在历史记录中恰好出现了一次！

除了原始数据外，网站还会显示所有评分的汇总信息——评分总数 $n$ 以及它们的中位数。中位数是根据网店排名的标准方法计算的。评分序列首先按非递减顺序排列：$a'_1 \le a'_2 \le \dots \le a'_n$。然后： 如果评分数量为奇数，则中位数为排序序列中的中间值，即 $a'_{\frac{1}{2}(n+1)}$。 如果评分数量为偶数，则中位数为排序序列中两个中间值的算术平均值，即 $\frac{1}{2}(a'_{\frac{1}{2}n} + a'_{\frac{1}{2}n+1})$。

由于 Bajtek 收到的每个从 $1$ 到 $n$ 的评分恰好出现一次，不难算出他商店目前所有评分的中位数正好是 $\frac{1}{2}(n + 1)$。

Bajtek 公司的一名黑客成功入侵了排名系统，因此他有机会影响系统的一些参数。具体来说，他可以删除商店的一些最旧的评分和一些最新的评分。更准确地说，黑客可以选择两个整数参数 $\ell$ 和 $r$ ($1 \le \ell \le r \le n$)，并仅在排名系统中保留评分 $a_\ell, a_{\ell+1}, \dots, a_r$。此时，排名系统会更新剩余所有评分的数量和中位数。

此外，黑客从系统的源代码中得知，在排名主页上，最大化目标函数的商店会获得更高的曝光度，目标函数等于评分数量与评分中位数的两倍之和（即 $X + 2 \cdot Y$，其中 $X$ 是评分数量，$Y$ 是评分中位数）。不难发现，无论评分数量和中位数如何，目标函数始终为整数。

请帮助 Bajtek 在排名系统中定位他的商店！确定黑客干预后目标函数的最大可能值。同时，请指出黑客可以通过多少种不同的方式获得该目标函数值。如果两种方式中参数 $\ell$ 或 $r$ 至少有一个不同，则认为这两种方式是不同的。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le n$)，表示商店的各个评分。从 $1$ 到 $n$ 的每个评分在序列中恰好出现一次。

输出格式

输出两个整数——黑客攻击后目标函数的最大值，以及可以达到该值的不同方式的数量。

样例

输入 1

5
1 4 3 5 2

输出 1

11 5

说明 1

为了获得等于 $11$ 的目标函数值，黑客可以选择以下参数对 $(\ell, r)$： $(1, 4)$ – 剩余评分为 $1, 4, 3, 5$，因此评分数量 $X = 4$，中位数 $Y = \frac{7}{2}$。 $(1, 5)$ – 剩余评分为 $1, 4, 3, 5, 2$。此时 $X = 5$ 且 $Y = 3$。 $(2, 4)$ – 剩余评分为 $4, 3, 5$。此时 $X = 3$ 且 $Y = 4$。 $(2, 5)$ – 剩余评分为 $4, 3, 5, 2$。此时 $X = 4$ 且 $Y = \frac{7}{2}$。 * $(4, 4)$ – 仅剩余评分 $5$。此时 $X = 1$ 且 $Y = 5$。

在上述每种情况下，目标函数的值均为 $X + 2 \cdot Y = 11$。