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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

20D. Density Two

Constraints

Input

Output

Samples

20D. Density Two

Constraints

Input

Output

Samples