Frogs

수직선 위에 $N$마리의 개구리가 있다. $i$번 개구리는 처음에 정수 좌표 $X_i$에 있다.

다음 조작을 $0$번 이상 수행할 수 있다.

• 두 개구리 $i,j$ ($1\le i \textcolor{red}{<} j\le N$)를 고른다. 좌표 $2X_j-X_i$가 번 개구리가 그곳으로 점프한다.

개구리들은 가능한 한 원점 가까이 모이려고 한다. 조작을 마친 뒤, $\displaystyle\max_{1\le i\le N}|X_i|$의 가능한 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

정답을 출력한다.

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