/ 
Time Limit: 2 sec / Memory Limit: 512 MB
配点 : 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 を単独で出力せよ。
入力例 1
4 3 4 3 2
出力例 1
6 8
例えば、ゲームの開始時に子供が 6 人いた場合、以下のように進行します。
- ラウンド 1 では、6 人の子供たちが 3 人組を 2 つ作り、誰も脱落しません。
- ラウンド 2 では、6 人の子供たちが 4 人組を 1 つ作り、2 人が脱落します。
- ラウンド 3 では、4 人の子供たちが 3 人組を 1 つ作り、1 人が脱落します。
- ラウンド 4 では、3 人の子供たちが 2 人組を 1 つ作り、1 人が脱落します。
最後まで残った二人が勝者となります。
入力例 2
5 3 4 100 3 2
出力例 2
-1
このような状況はありえません。 特に、ゲームの開始時の子供たちの人数が 100 人未満の場合は、ラウンド 3 で全員が脱落します。
入力例 3
10 2 2 2 2 2 2 2 2 2 2
出力例 3
2 3
Score : 500 points
Problem Statement
An adult game master and N children are playing a game on an ice rink. The game consists of K rounds. In the i-th round, the game master announces:
- Form groups consisting of A_i children each!
Then the children who are still in the game form as many groups of A_i children as possible. One child may belong to at most one group. Those who are left without a group leave the game. The others proceed to the next round. Note that it's possible that nobody leaves the game in some round.
In the end, after the K-th round, there are exactly two children left, and they are declared the winners.
You have heard the values of A_1, A_2, ..., A_K. You don't know N, but you want to estimate it.
Find the smallest and the largest possible number of children in the game before the start, or determine that no valid values of N exist.
Constraints
- 1 \leq K \leq 10^5
- 2 \leq A_i \leq 10^9
- All input values are integers.
Input
Input is given from Standard Input in the following format:
K A_1 A_2 ... A_K
Output
Print two integers representing the smallest and the largest possible value of N, respectively, or a single integer -1 if the described situation is impossible.
Sample Input 1
4 3 4 3 2
Sample Output 1
6 8
For example, if the game starts with 6 children, then it proceeds as follows:
- In the first round, 6 children form 2 groups of 3 children, and nobody leaves the game.
- In the second round, 6 children form 1 group of 4 children, and 2 children leave the game.
- In the third round, 4 children form 1 group of 3 children, and 1 child leaves the game.
- In the fourth round, 3 children form 1 group of 2 children, and 1 child leaves the game.
The last 2 children are declared the winners.
Sample Input 2
5 3 4 100 3 2
Sample Output 2
-1
This situation is impossible. In particular, if the game starts with less than 100 children, everyone leaves after the third round.
Sample Input 3
10 2 2 2 2 2 2 2 2 2 2
Sample Output 3
2 3