← 返回题目列表

AtCoder · agc020_b

B. 溜冰场游戏

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

分数: 500 点

问题陈述

成人游戏高手和 N 孩子们正在溜冰场上玩游戏。 游戏由 K 回合。 在 i第轮,游戏主宣布:

  • 形成组,包括 A_i 小朋友们各自好!

然后仍在游戏中的孩子们组成尽可能多的小组 A_i 孩子越多越好。 一个孩子最多可以属于一个组。 没有组的人离开游戏。其他人进入下一轮。 请注意,有可能没有人在某个回合中离开游戏。

最后,经过 K第一轮,只剩下两个孩子,他们被宣布为获胜者。

您已经听说过以下价值观 A_1, A_2, ..., A_K。你不知道 N,但您想估计它。

在开始之前找到游戏中可能的最小和最大儿童数量,或者确定没有有效值 N 存在。

约束

  • 1 \leq K \leq 10^5
  • 2 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

K
A_1 A_2 ... A_K

输出

打印两个整数,分别代表以下的最小和最大可能值 N分别是 或单个整数 -1 如果所描述的情况不可能。


示例输入 1

4
3 4 3 2

示例输出 1

6 8

例如,如果游戏开始于 6 孩子们,那么它的过程如下:

  • 第一轮, 6 儿童表格 2 组 3 孩子们,没有人离开游戏。
  • 在第二轮中, 6 儿童表格 1 组 4 儿童,以及 2 孩子们离开游戏。
  • 第三轮, 4 儿童表格 1 组 3 儿童,以及 1 孩子离开游戏。
  • 第四轮, 3 儿童表格 1 组 2 儿童,以及 1 孩子离开游戏。

最后 2 孩子们被宣布为获胜者。


示例输入 2

5
3 4 100 3 2

示例输出 2

-1

这种情况是不可能的。 特别是,如果游戏开始时少于 100 孩子们,第三轮结束后大家都离开了。


示例输入 3

10
2 2 2 2 2 2 2 2 2 2

示例输出 3

2 3