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.

4
3 4 3 2

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.

5
3 4 100 3 2

-1

This situation is impossible. In particular, if the game starts with less than $100$ children, everyone leaves after the third round.

10
2 2 2 2 2 2 2 2 2 2

2 3