CF2087G Esports in Berland

最近，电子竞技在 Berland 被正式认可为一项体育运动，并且开始定期举办比赛。借着这股热潮，Monocarp 也决定参加即将到来的比赛（毕竟奖金从来不会嫌多）。 在接下来的 $n$ 天里，每天都会举行一场比赛。Monocarp 想要参加所有比赛，但遗憾的是，他当前的技能水平 $s$ 为 $0$。与此同时，Monocarp 在比赛中能获得的奖金取决于他的技能水平。因此，Monocarp 决定可以牺牲参加部分比赛的机会，在这些天里进行训练以提升自己的技能水平。 具体来说，在第 $i$ 天，Monocarp 可以： - 参加第 $i$ 场比赛，获得 $a_i + s$ 单位的奖金，其中 $s$ 是他当前的技能水平； - 或者跳过这场比赛进行训练：Monocarp 不会获得任何奖金，但他的技能水平 $s$ 会增加 $1$。 请帮助 Monocarp 计算他在最优训练计划下能够获得的最大总收入，以及达到该收入的训练方案数。若存在某一天在一个方案中是训练日、在另一个方案中是比赛日，则这两个训练计划被认为是不同的。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示将要举行比赛的天数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^6$），表示 Monocarp 期望获得的每场比赛的基础奖金。

输出两个整数，分别表示 Monocarp 能够获得的最大总收入，以及达到该收入的训练方案数。 由于方案数可能过大，请输出对 $998\,244\,353$ 取模后的结果。

在第一个样例中，Monocarp 可以选择参加或跳过比赛——无论哪种情况，他都能获得 $0$ 单位的奖金。 在第二个样例中，最优方案是直接参加比赛。 在第三个样例中，有两种训练方案。Monocarp 可以： 1. 前两天训练，剩下的天数参加比赛：Monocarp 将获得 $3 \cdot (0 + 2) = 6$ 单位的奖金； 2. 前三天都训练：Monocarp 将获得 $2 \cdot (0 + 3) = 6$ 单位的奖金。 在第四个样例中，Monocarp 可以选择全部参加比赛，或者跳过任意一天。 由 ChatGPT 4.1 翻译