I. Step
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given $$$n$$$ rings, and the length of the $$$i$$$-th ring is $$$p_i(1\le i \le n)$$$. For the $$$i$$$-th ring, the next position of $$$p_i$$$ is $$$1$$$. At the very beginning, there is a pony at position $$$1$$$ of each ring, and the ponies move faster and faster every day.

Specifically, a pony moves $$$1$$$ step on the first day, and $$$2$$$ steps on the second day, and so on. Formally, the pony will move $$$k$$$ steps on the $$$k$$$-th day for $$$k \in \mathbb{N}^*$$$.

It is clear that on a certain day, all the ponies will arrive at position $$$1$$$. Now Miku wants to know the earliest day $$$m$$$ (except day $$$0$$$) when all the $$$n$$$ ponies will arrive at position $$$1$$$.

Input

The first line of the input contains a single positive integer $$$n$$$ ($$$1 \le n\leq 10^5$$$) – the number of rings.

The second line of the input contains $$$n$$$ positive integers $$$p_i$$$ $$$(1 \leq p_i\leq 10^7)$$$ – the length of each rings.

It is guaranteed that $$$\operatorname{lcm}(p_1,p_2,...,p_n)\leq 10^{18}$$$. Remind that $$$\operatorname{lcm}(p_1,p_2,\ldots,p_n)$$$ stands for the least common multiple (LCM) of $$$\{p_1,p_2,\ldots,p_n\}$$$.

Output

Output a single positive integer denoting the earliest day that all the $$$n$$$ ponies will arrive at position $$$1$$$.

Examples
Input
3
3 6 9
Output
8
Input
4
114 514 1919 810
Output
26138699