C. Balanced Difference
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of $$$n$$$ elements, you want to partition $$$a$$$ into $$$2$$$ subsequences of size at least $$$2$$$ such that every element in the array belongs to exactly one subsequence and the difference between the maximum and minimum element in each subsequence is the same. Print the maximum possible difference or $$$-1$$$ if a partition cannot be found.

Input

The first line includes one number $$$n$$$ ($$$2 \le n \le 10^5$$$), the length of the array. The second line contains $$$n$$$ space separated numbers representing $$$a$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Output

Print one number representing the maximum difference of a valid partition.

Example
Input
5
4 7 2 9 5
Output
5
Note

In the example, we can divide the array into $$$[2, 5, 7]$$$ and $$$[4, 9]$$$. The difference between the maximum and minimum in each partition is equal to $$$5$$$.