← 返回题目列表

Codeforces · 2087/G

G. 伯兰的电子竞技

中文机器翻译题面 查看原题

近日,电子竞技在柏林被认定为正式体育项目,并开始定期举办比赛。乘着人气的浪潮,Monocarp也决定参加即将到来的比赛(而且奖品从来没有伤害过任何人)。

在接下来的$$$n$$$天内,将举行一场比赛。 Monocarp 很想参加所有这些活动,但不幸的是,他目前的技能等级 $$$s$$$ 是 $$$0$$$。同时,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$$$ 为模打印它。

示例

输入
复制

1
0

输出
复制

0 2

输入
复制

1
42

输出
复制

42 1

输入
复制

5
0 0 0 0 0

输出
复制

6 2

输入
复制

6
5 4 3 2 1 0

输出
复制

15 7

输入
复制

10
5 9 0 3 2 0 2 2 9 9

输出
复制

53 3

注意

在第一个示例中,Monocarp 可以参加或跳过比赛 - 在这两种情况下,他都将获得 $$$0$$$ 单位。

在第二个示例中,简单地参与竞争是最佳的。

在第三个示例中,有两个培训计划。单果罐头

  1. 要么在前两天进行训练,然后在剩下的日子里参加比赛:Monocarp 将获得 $$$3 \cdot (0 + 2) = 6$$$ 单位;
  2. 或前三天训练:Monocarp 将赚取 $$$2 \cdot (0 + 3) = 6$$$ 单位。

在第四个示例中,Monocarp 可以参加所有比赛,也可以跳过任何一天。