← 返回题目列表

AtCoder · abc272_g

G. 又一个mod M

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个序列 A=(A_1,A_2,\dots,A_N) 长度 N 由正整数组成,其中元素 A 是不同的。

您将选择一个正整数 M 之间 3 和 10^9 (含)执行以下操作一次:

  • 对于每个整数 i 这样 1 \le i \le N,替换 A_i 与 A_i \bmod M.

你可以选择一个 M 这样 A 运行后满足以下条件? 如果可以的话,找一个这样的 M.

  • 存在一个整数 x 这样 x 是大多数 A.

这里,一个整数 据说 x 是其中的大多数 A 如果整数的个数 i 这样 A_i = x 大于整数个数 i 这样 A_i \neq x.

约束

  • 3 \le N \le 5000
  • 1 \le A_i \le 10^9
  • 的元素 A 是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

如果存在 M 满足条件,打印这样的 M。 否则,打印 -1.


样本输入 1

5
3 17 8 14 10

示例输出 1

7

如果你让 M=7 要执行该操作,您将拥有 A=(3,3,1,0,3),其中 3 是大多数 A,所以 M=7 满足条件。


示例输入 2

10
822848257 553915718 220834133 692082894 567771297 176423255 25919724 849988238 85134228 235637759

示例输出 2

37

示例输入 3

10
1 2 3 4 5 6 7 8 9 10

示例输出 3

-1