마지막 문제

때는 3023년, PPC 출제진은 PPC에 출제할 $N$개의 문제를 신중하게 골랐다. 각 문제에는 $1$ 이상 $10^9$ 이하의 정수로 나타낸 난이도가 있으며, $N$개 문제의 난이도는 모두 다르다. 난이도를 나타내는 수가 작을수록 쉬운 문제이다.

출제진은 마지막 문제를 하나 추가할 것이다. 이 문제의 난이도는 다음 두 조건을 모두 만족해야 한다.

기존 $N$개 문제 중 어느 문제의 난이도와도 같지 않아야 한다.

기존 문제 중 가장 쉬운 문제보다 쉽지 않고, 가장 어려운 문제보다 어렵지 않아야 한다.

출제진은 난이도 분포를 최대한 고르게 만들고 싶어 한다. 그래서 기존 문제들과의 난이도 차이의 최솟값이 가장 커지도록 난이도를 고른다. 이 최댓값을 만드는 난이도가 여러 개이면 그중 가장 낮은 난이도를 고른다. 마지막 문제의 난이도를 구하라.

첫 번째 줄에 준비된 문제의 수 $N$ ($2 \leq N \leq 3\ 000$)이 주어진다.

두 번째 줄에 서로 다른 $N$개의 정수 $A_1, A_2, \ldots, A_N$ ($1 \leq A_i \leq 10^9$)이 공백으로 구분되어 주어진다.

마지막 문제의 난이도를 출력한다. 출제진이 마지막 문제를 추가할 수 없다면 -1을 출력한다.

이 문제는 이번 대회의 마지막 문제이다.