题目描述
Alice 有 n 个正整数,数字从 1∼n 编号,分别为 a1,a2,…,an。
Bob 刚学习取模运算,于是便拿这 n 个数进行练习,他写下了所有
aimodaj(1≤i,j≤n∧i=j)
的值,其中 mod 表示取模运算。
Alice 想知道所有的结果中,严格次大值是多少。将取模后得到的所有值进行去重,即相同的结果数值只保留一个,剩余数中第二大的值就称为严格次大值。
输入格式
第一行一个正整数 n,表示数字个数。
第二行 n 个正整数表示 ai。
输出格式
仅一行一个整数表示答案。
若若取模结果去重后剩余数字不足两个,则输出 −1。
4
4 5 5 6
4
4
1 1 1 1
-1
7
12 3 8 5 7 20 15
12
提示
【数据范围】
对于 40% 的数据,1≤n,ai≤100;
对于 70% 的数据,1≤n≤3000,1≤ai≤105;
对于 100% 的数据,3≤n≤2×105,1≤ai≤109。
【样例 1 解释】
所有取模的结果为 {4,4,4,1,0,5,1,0,5,2,1,1}。
去重后有:{0,1,2,4,5},结果为 4。