题目描述

一位成年游戏大师和 $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