3645. 莫干山奇遇

单点时限: 2.0 sec

内存限制: 512 MB

出题人当然是希望出的题目有关 oxx,于是想方设法给题目配上一些有关 oxx 的背景故事,使得它看起来不那么无趣。但有的时候却无法引入合适的小姐姐,使得 oxx 显得非常可怜。所以出题人删除了故事,只留下一个枯燥乏味的数学问题。

【故事已删除】

给一个长度为 n 的序列 a1,a2,,an,求一个长度为 m 的序列 b1,b2,,bm 使得:

  • a1,a2,,anb1,b2,,bm 的子序列(不一定连续),且
  • 存在常数 p>0 使得 b1,b2,,bm 是一个 p-莫干山序列。

序列 s1,s2,,snp-莫干山序列,当且仅当:存在 0x<p 对于 1in 满足 si=(x+i)modp

m 的最小值。

输入格式

第一行一个整数 n (1n2105)。

第二行 n 个整数用空格隔开 a1,a2,,an (0ai109)。

输出格式

输出最小的 m

样例

Input
2
0 2
Output
3
Input
3
0 2 0
Output
4
Input
1
0
Output
1
Input
10
0 1 2 3 5 6 7 8 9 1000000000
Output
1000000001
Input
3
0 1 2
Output
3

提示

样例 1: [0, 1, 2].

样例 2: [0, 1, 2, 0].

样例 3: [0].

340 人解决,425 人已尝试。

415 份提交通过,共有 1939 份提交。

2.5 EMB 奖励。

创建: 6 年,6 月前.

修改: 6 年,6 月前.

最后提交: 3 周,3 天前.

来源: EOJ Monthly 2018.10

题目标签