#P1149. Hash Function

Hash Function

Background

2021nowcoder多校day1 数据手造,如果想品尝原汁原味的数据,请在nowcoder购买

Description

For a given set S={a0,a1,a2,...,an1}S = \{a_0, a_1, a_2, ..., a_{n-1}\}, we called a hash function fS(x)f_S(x)perfect hash function of S , if it satisfies0i<j<n,fS(ai)fS(aj) \forall 0 \leq i < j < n, f_S(a_i) \neq f_S(a_j).

Given a set S with non-negative integers, please find the minimum positive integer seed that function hseed(x)=xmodseedh_{seed}(x) = x \mod seed is a perfect hash function of S.

Note: Six more test cases are added after contest.

Format

Input

The first line of input contains one integer nn, describing the size of set S.

The second line contains n(1n500000)n(1 \leq n \le 500000) integers a0,...,an1a_0,...,a_{n-1}, describing the elements in S.

It is guaranteed that$\forall 0 \leq i < j < n, a_i \ne a_j, 0 \le a_i \le 500000$.

Output

Output one integer in a line, indicating the answer.

Samples

3
2 3 4
3
3
1 2 4
4
10
0 7 23 18 29 27 6 28 24 11
15

Limitation

1s, 1024KiB for each test case.