Score : $600$ points

问题描述

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

你需要在 $3$ 到 $10^9$（包含）之间选择一个正整数 $M$ 来执行以下操作一次：

• 对于满足 $1 \le i \le N$ 的每个整数 $i$，将 $A_i$ 替换为 $A_i \bmod M$。

能否选择一个 $M$，使得操作后 $A$ 满足以下条件？如果可以，请找出这样的 $M$。

• 存在一个整数 $x$，它在 $A$ 中是多数。

这里，若整数 $x$ 在 $A$ 中满足其等于 $A_i$ 的整数个数大于不等于 $A_i$ 的整数个数，则称 $x$ 是 $A$ 中的多数。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$ consisting of positive integers, where the elements of $A$ are distinct.

You will choose a positive integer $M$ between $3$ and $10^9$ (inclusive) to perform the following operation once:

• For each integer $i$ such that $1 \le i \le N$, replace $A_i$ with $A_i \bmod M$.

Can you choose an $M$ so that $A$ satisfies the following condition after the operation? If you can, find such an $M$.

• There exists an integer $x$ such that $x$ is the majority in $A$.

Here, an integer $x$ is said to be the majority in $A$ if the number of integers $i$ such that $A_i = x$ is greater than the number of integers $i$ such that $A_i \neq x$.

Constraints

• $3 \le N \le 5000$
• $1 \le A_i \le 10^9$
• The elements of $A$ are distinct.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\dots$ $A_N$

Output

If there exists an $M$ that satisfies the condition, print such an $M$. Otherwise, print $-1$.

Sample Input 1

5
3 17 8 14 10

Sample Output 1

7

If you let $M=7$ to perform the operation, you will have $A=(3,3,1,0,3)$, where $3$ is the majority in $A$, so $M=7$ satisfies the condition.

Sample Input 2

10
822848257 553915718 220834133 692082894 567771297 176423255 25919724 849988238 85134228 235637759

Sample Output 2

37

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

-1

update @ 2024/3/10 11:28:48