分数: 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