题目描述

在滑冰场上，一名大人主持和 $N$ 名小孩进行游戏。游戏分为 $K$ 轮，第 $i$ 轮主持人会说：

• 请组成 $A_i$ 人的小组！

然后，尚未被淘汰的小孩会尽量多地组成每组有 $A_i$ 人的小组。每个人只能加入一个小组。不能加入小组的小孩会被淘汰，其他人进入下一轮。可能出现某一轮没有人被淘汰的情况。

最终，即第 $K$ 轮后，剩下 $2$ 个人，他们成为胜者。

你得到了 $A_1, A_2, \ldots, A_K$ 的值，但并不知道 $N$ 的具体值。请你推测游戏开始时小孩的人数 $N$ 可能的最小值和最大值。或者，判断不存在可能的 $N$。

输入格式

输入从标准输入按以下格式给出：

$K$ $A_1$ $A_2$ $...$ $A_K$

输出格式

请输出可能的 $N$ 的最小值和最大值，中间用一个空格隔开。如果不存在可能的 $N$，仅输出 $-1$。

样例 1

输入

4
3 4 3 2

输出

6 8

样例 2

输入

5
3 4 100 3 2

输出

-1

样例 3

输入

10
2 2 2 2 2 2 2 2 2 2

输出

2 3

说明/提示

限制条件

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

样例解释 1

例如，游戏开始时有 $6$ 个小孩时，游戏过程如下：

• 第 $1$ 轮，$6$ 个小孩组成两个 $3$ 人小组，无人淘汰。
• 第 $2$ 轮，$6$ 个小孩组成一个 $4$ 人小组，有 $2$ 人被淘汰。
• 第 $3$ 轮，$4$ 个小孩组成一个 $3$ 人小组，有 $1$ 人被淘汰。
• 第 $4$ 轮，$3$ 个小孩组成一个 $2$ 人小组，有 $1$ 人被淘汰。
• 最后剩下的两个人获胜。

样例解释 2

这种情况不存在。例如，如果游戏开始时小孩人数不足 $100$ 人，在第 $3$ 轮所有人都会被淘汰。

由 ChatGPT 5 翻译