Background

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

Description

For a given set $S = \{a_0, a_1, a_2, ..., a_{n-1}\}$, we called a hash function $f_S(x)$perfect hash function of S , if it satisfies$\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 $h_{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 $n$, describing the size of set S.

The second line contains $n(1 \leq n \le 500000)$ integers $a_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.