#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Density Two - Repovive Premier Round 7 | Repovive

20D. Density Two

2000 pts2s256 MB

There are $n$ points on a number line. Point $i$ is located at coordinate $a_i$ .

For each point $i$ , you must choose a closed interval $I_i=[l_i,r_i]$ with integer endpoints. The length of this interval must be exactly $a_i$ , and it must contain the point located at coordinate $a_i$ . In other words, $r_i-l_i=a_i$ and $l_i \le a_i \le r_i$ must both hold.

For a real number $x$ , define its density $d(x)$ as the number of intervals whose interior contains $x$ :

d(x)=\left|{i \mid l_i<x<r_i}\right|.

Notice that the endpoints of an interval are not counted. For example, the intervals $[0,2]$ and $[2,5]$ do not overlap according to this definition.

A choice of intervals is called valid if $d(x)\le 2$ for every real number $x$ .

For a valid choice, let $R=\max_{1\le i\le n}r_i$ . Find the minimum possible value of $R$ . If no valid choice of intervals exists, output $-1$ .

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 2 \times 10^5$

Input

n

a_1 \quad a_2 \quad \ldots \quad a_n

Output

Output one integer: the minimum possible value of $R$ , or $-1$ if no valid choice exists.

Samples

Input

3
1 2 3

Explanation

Choose the intervals $[0,1]$ , $[1,3]$ , and $[0,3]$ . Their maximum right endpoint is $3$ , and the density never exceeds $2$ .

Every interval corresponding to the point at coordinate $3$ has right endpoint at least $3$ , so a smaller answer is impossible.

Output

Input

5
1 1 1 1 1

Explanation

An interval of length $1$ with integer endpoints that contains coordinate $1$ must be either $[0,1]$ or $[1,2]$ . At most two chosen intervals can have each of these interiors, so five intervals cannot be placed validly.

Output

-1

Input

6
1 1 2 2 4 4

Explanation

Use two identical groups of intervals: $[0,1]$ , $[1,3]$ , and $[3,7]$ . Each group has disjoint interiors, so together the density is at most $2$ and the maximum right endpoint is $7$ .

The total length of all intervals is $14$ . Since all intervals lie between $0$ and $R$ and the density is at most $2$ , their total length cannot exceed $2R$ . Therefore, $R$ cannot be smaller than $7$ .

Output

There are $n$ points on a number line. Point $i$ is located at coordinate $a_i$ .

For a real number $x$ , define its density $d(x)$ as the number of intervals whose interior contains $x$ :

d(x)=\left|{i \mid l_i<x<r_i}\right|.

Notice that the endpoints of an interval are not counted. For example, the intervals $[0,2]$ and $[2,5]$ do not overlap according to this definition.

A choice of intervals is called valid if $d(x)\le 2$ for every real number $x$ .

For a valid choice, let $R=\max_{1\le i\le n}r_i$ . Find the minimum possible value of $R$ . If no valid choice of intervals exists, output $-1$ .

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 2 \times 10^5$

n

a_1 \quad a_2 \quad \ldots \quad a_n

Output one integer: the minimum possible value of $R$ , or $-1$ if no valid choice exists.

Choose the intervals $[0,1]$ , $[1,3]$ , and $[0,3]$ . Their maximum right endpoint is $3$ , and the density never exceeds $2$ .

Every interval corresponding to the point at coordinate $3$ has right endpoint at least $3$ , so a smaller answer is impossible.

Use two identical groups of intervals: $[0,1]$ , $[1,3]$ , and $[3,7]$ . Each group has disjoint interiors, so together the density is at most $2$ and the maximum right endpoint is $7$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

20D. Density Two

Constraints

Input

Output

Samples

20D. Density Two

Constraints

Input

Output

Samples