Limits 1s, 512 MB

Byang is the chief software engineer at Toad Incorporated. His grandmother is planning to give him a visit. But his grandmother is old and weak. She walks very slowly and cannot take long footsteps anymore. And most importantly, she hates “Kochuripana”.

Byang discovered that the only road to his house has some “Kochuripana”. He took notes on where the “Kochuripanas” are located. Then he passed the notes to you and told you that his grandmother always takes equal sized footsteps. Byang wonders what is the minimum length of footstep his grandmother can take so that she does not have to step on any “Kochuripana”. Now it is your job to find the answer.

Let’s denote positive X-axis as the only road to Byang’s house. Byang’s grandmother will start to walk from point 0. There are NN “Kochuripanas” at integer points X1X_1, X2X_2,...., XNX_N. You have to find the minimum length of footstep Byang’s grandmother can take so that she does not step on any “Kochuripana”. Note that, if Byang’s grandmother takes footsteps of size kk, then she will step on these points: 0, kk, 2k2k, 3k3k, 4k4k... Also note that, Byang’s grandmother always takes footsteps of integer length.

Input

On the first line a positive integer NN (1N1061 \le N \le 10^6)

On the next N lines there will be one integer XiX_i (1Xi1071 \le X_i \le 10^7).

Output

Only one line with one integer, the minimum length of footstep Byang's grandmother should take to avoid "Kochuripana".

Sample

InputOutput
4
2
3
7
8
5

Submit

Login to submit.

Statistics

33% Solution Ratio
saitamaEarliest, Dec '15
ItzRAYFastest, 0.0s
PsychoKillerLightest, 1.3 MB
ItzRAYShortest, 334B
Toph uses cookies. By continuing you agree to our Cookie Policy.