Last Problem

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given N distinct difficulties, find the lowest integer in their range that maximizes the minimum distance to all of them, or -1 if none exists.

Level: Easy3 of 10
Topics: Sorting, Greedy
Solved: No attempts yet

Problem

In the year 3023, the PPC problem setters carefully chose $N$ problems to use in PPC. Each problem has a difficulty given as an integer from $1$ to $10^9$ , and the $N$ difficulties are all distinct. A smaller difficulty number means an easier problem.

Problem

The setters will add one final problem. Its difficulty must satisfy both of the following conditions.

It must differ from the difficulty of every existing problem.

It must not be easier than the easiest existing problem, and it must not be harder than the hardest existing problem.

The setters want the difficulty spread to be as even as possible. They will choose the difficulty that maximizes the minimum difference to the existing problems. If several difficulties tie for that maximum, they will choose the lowest one. Find the difficulty of the final problem.

Input

The first line contains $N$ ( $2 \leq N \leq 3\ 000$ ), the number of prepared problems.

The second line contains $N$ distinct integers $A_1, A_2, \ldots, A_N$ ( $1 \leq A_i \leq 10^9$ ), separated by spaces.

Output

Print the difficulty of the final problem. If the setters cannot add a final problem, print -1.

Hint

This is the last problem of this contest.

Examples3

Example 1
Input
```
3
1 5 8
```
Expected output
```
3
```
Example 2
Input
```
4
2 5 3 4
```
Expected output
```
-1
```
Example 3
Input
```
3
8 3 6
```
Expected output
```
4
```