#490 Frogs

Loading problem...

Preparing the statement, recent submissions, and submit form.

#490 Frogs

DOJ/DOJ Contest/DOJ Contest 6

Authors: pk661

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

There are $N$ frogs on a number line. Frog $i$ is initially at integer coordinate $X_i$ .

You may perform the following operation any number of times, possibly zero.

Choose two frogs $i,j$ ( $1\le i \textcolor{red}{<} j\le N$ ). If coordinate $2X_j-X_i$ is , frog jumps there.

The frogs want to gather as close to the origin as possible. After all operations, find the minimum possible value of $\displaystyle\max_{1\le i\le N}|X_i|$ .

Input

The input is given in the following format:

$N$ $X_1\ X_2\ \cdots\ X_N$

Output

Output the answer.

Constraints

$1\le N\le 200\,000$ .
$-10^9\le X_i\le 10^9$ ().

Subtasks

#	Score	Constraints
1	3	$\|X_i\|\le\|X_N\|$ for every $1$ .

Samples

Sample 1

Input

3
10 -1 2

Output

Sample 2

Input

5
-7 9 4 5 -3

Output

Editorial

View editorial

\leq

i

\leq

N

1\le i\le N