题目描述

江桥终于升入了铁一中学，迎来了他的开学军训。

又到了集合的时间，江桥所在连队的教官在进行整队。

江桥的连一共有 $n$ 名同学，其中第 $i$ 名同学的身高为 $a_i$。 教官想把他们排成一列，以便练习正步。 教官觉得，如果一个区间内各同学的身高不一致，那么看起来就会不太整齐。他定义了一个序列的不整齐度，表示所有区间的身高极差之和，这里极差指的是最大值与最小值的差值。 教官想将这 $n$ 名不同的同学排成一列，使得整个队列的不整齐度最小，同时他还想知道一共有多少种不同的排法。

但是，庞大的计算量使得教官无法快速完成这个任务，于是他决定向整个连队中编程水平最高的江桥求助。江桥也不会，于是他偷偷向你发起了求助。

形式化题意： 给 你 一 个 长 度 为 $n$ 的 序 列 $a_1, a_2, · · · , a_n$，问 有 多 少 个 排 列 $p$ 使 得 $\sum_{l = 1}^{n}\sum_{r = l}^{n}max\{a_{p_l} , a_{p_{l+1}} , · · · , a_{p_r}\} − min\{ a_{p_l} , a_{p_{l+1}} , · · · , a_{p_r}\}$ 最小。

输出最小值、以及方案数对 998244353 取模后的结果。

如果你不了解什么是取模，可以参考以下代码（C++）：

//求c = a + b 对 mod 取模：
c = (a + b) % mod;

输入格式

第一行一个整数 $n$, 表示学生个数。

第二行 $n$ 个整数 $a_1, a_2, · · · , a_n$, 表示这 $n$ 名同学的身高。

输出格式

共一行，两个整数，分别为队列不整齐度的最小值、满足不整齐度最小的方案数对 $998244353$ 取模后的结果。请注意，不整齐度的最小值不需要取模。

2
1 2

1 2

9
9 9 8 2 4 4 3 5 3

114 16

样例解释

对于第一个样例，直接按输入顺序排列，可以得到三个区间 $[1],[2],[1,2]$，其极差分别为 $0,0,1$，得到的不整齐度是 $1$，可以证明，这就是最小值。另一种方案是 $[2,1]$，不整齐度也是 $1$。

数据规模与约定

下发文件

下发文件对应子任务 $8$。

本题包含subtask，有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1\leq n,a_i \leq 10^6$。