近日,电子竞技在柏林被认定为正式体育项目,并开始定期举办比赛。乘着人气的浪潮,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$$$ 为模打印它。
示例
输入复制
10
输出复制
0 2
输入复制
142
输出复制
42 1
输入复制
50 0 0 0 0
输出复制
6 2
输入复制
65 4 3 2 1 0
输出复制
15 7
输入复制
105 9 0 3 2 0 2 2 9 9
输出复制
53 3
注意
在第一个示例中,Monocarp 可以参加或跳过比赛 - 在这两种情况下,他都将获得 $$$0$$$ 单位。
在第二个示例中,简单地参与竞争是最佳的。
在第三个示例中,有两个培训计划。单果罐头
- 要么在前两天进行训练,然后在剩下的日子里参加比赛:Monocarp 将获得 $$$3 \cdot (0 + 2) = 6$$$ 单位;
- 或前三天训练:Monocarp 将赚取 $$$2 \cdot (0 + 3) = 6$$$ 单位。
在第四个示例中,Monocarp 可以参加所有比赛,也可以跳过任何一天。