问题 4757 --次大值

4757: 次大值

题目描述

  Alice 有 $n$ 个正整数,数字从 $1 \sim n$ 编号,分别为 $a_1,a_2, \dots , a_n$。  
Bob 刚学习取模运算,于是便拿这 $n$ 个数进行练习,他写下了所有$a_i \bmod a_j (1 \le i,j \le n ∧ i \neq j)$的值,其中 $\bmod$ 表示取模运算。 
Alice 想知道所有的结果中,严格次大值是多少。将取模后得到的所有值进行去重,即相同的结果数值只保留一个,剩余数中第二大的值就称为严格次大值。

输入

第一行一个正整数 $n$,表示数字个数。
第二行 $n$ 个正整数表示 $a_i$。

输出

仅一行一个整数表示答案。
若取模结果去重后剩余数字不足两个,则输出 $-1$。

样例输入输出

输入#1 复制
4
4 5 5 6
输出#1 复制
4
输入#2 复制
4
1 1 1 1
输出#2 复制
-1
输入#3 复制
7
12 3 8 5 7 20 15
输出#3 复制
12

提示

【样例 1 解释】 所有取模的结果为 $\{4,4,4,1,0,5,1,0,5,2,1,1\}$。
去重后有:$\{0,1,2,4,5 \}$,结果为 $4$。
【数据规模与约定】 对于 $40\%$ 的数据,$1\le n,a_i \le 100$;
对于 $70\%$ 的数据,$1\le n \le 3000$,$1\le a_i \le 10^5$;
对于 $100\%$ 的数据,$3 \le n \le 2\times 10^5$,$1\le a_i \le 10^9$。

序号 标题 作者 发表时间 费用 订购数 操作