配点 : $500$ 点

問題文

スケートリンクで、一人の大人の司会と $N$ 人の子供がゲームを行います。 ゲームは $K$ ラウンドからなり、ラウンド $i$ では司会が次のように言います。

• $A_i$ 人組を作って！

すると、まだ脱落していない子供たちは $A_i$ 人からなるグループをできるだけ多く組みます。 一人につき一つのグループにしか入れません。 グループに入れなかった子供たちは脱落し、その他は次のラウンドに進みます。 ラウンドで誰も脱落しないこともありえます。

最後まで、つまりラウンド $K$ のあとまで残ったのは $2$ 人で、彼らが勝者となりました。

あなたは $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$

Output

考えられる最小の $N$ の値と最大の $N$ の値をそれぞれ表す二つの整数を出力せよ。ただし、問題文で述べた状況が発生しえない場合は、整数 $-1$ を単独で出力せよ。

4
3 4 3 2

6 8

例えば、ゲームの開始時に子供が $6$ 人いた場合、以下のように進行します。

• ラウンド $1$ では、$6$ 人の子供たちが $3$ 人組を $2$ つ作り、誰も脱落しません。
• ラウンド $2$ では、$6$ 人の子供たちが $4$ 人組を $1$ つ作り、$2$ 人が脱落します。
• ラウンド $3$ では、$4$ 人の子供たちが $3$ 人組を $1$ つ作り、$1$ 人が脱落します。
• ラウンド $4$ では、$3$ 人の子供たちが $2$ 人組を $1$ つ作り、$1$ 人が脱落します。

最後まで残った二人が勝者となります。

5
3 4 100 3 2

-1

このような状況はありえません。 特に、ゲームの開始時の子供たちの人数が $100$ 人未満の場合は、ラウンド $3$ で全員が脱落します。

10
2 2 2 2 2 2 2 2 2 2

2 3