哈希表 (1s,512M)

小王有 $n$ 个互不相同的数 $a_1,a_2,\ldots,a_n$ 。小王希望把它们存到一个哈希表中。

小王要求哈希方式为把每个数 $x$ 映射到 $x\bmod q$ ，$q$ 为一选定的任意正整数。

但小王不喜欢哈希冲突，即要求不能有两个不同的数映射到了同一个值。

小王希望在没有哈希冲突的情况下，把哈希表开得尽量小，即选取一个最小的满足条件的 $q$ 。

但小王不会计算最小的 $q$，请你帮帮他。

输入第一行一个整数 $n$ 。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$ 。

输出一个整数，表示最小的 $q$ 。

对于 $10\%$ 的数据，$n=2$ 。

对于 $30\%$ 的数据，$n\leq 5000,a_i\leq 5000$ 。

对于 $60\%$ 的数据，$n\leq 5000,a_i\leq 10^6$ 。

对于另外 $40\%$ 的数据，$n,a_i\leq 10^5$ 。 对于 $100\%$ 的数据，$n\geq 2,\ \ n,a_i\leq 10^6$ 。

样例下载

file