题目背景

一股巨大的斥力袭来。全身上下仿佛分裂成了透明的碎片。

镜中有一个模糊的人影。是「你」吗？还是仅仅来源于幻觉？无从知道。你想要向前走，可对方却保持着极端的默契向后退去。当你让步时，对方却又赶了上来。

已经没有任何能量支撑你接着思考下去了。但朝着棱镜中央那丝微弱的光源，你无论如何都想要再靠近一点。此外，还有对面的另一个「你」......

题目描述

给定一个长为 $n$ 的整数序列 $a_1,\ldots,a_n$。你可以进行任意多次操作（也可以不操作），每次操作你需要在如下两种形式中进行选择：

• 全局自增 $1$：对每个 $1 \leq i \leq n$，将 $a_i$ 自增 $1$；
• 全局自减 $1$：对每个 $1 \leq i \leq n$，将 $a_i$ 自减 $1$。

你希望让操作后的 $\max\limits_{i=1}^n \lvert a_i \rvert$ 最小，即最小化所有 $\lvert a_i\rvert$ 的最大值，其中，$\lvert a_i\rvert$ 表示 $a_i$ 的绝对值。你只需要计算这个最小化后的结果即可。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个整数 $a_1,\ldots,a_n$，描述给定的序列。

输出格式

仅一行，一个整数，表示 $\max\limits_{i=1}^n \lvert a_i \rvert$ 的最小值。

5
-5 -2 0 2 3

4

6
1 -1 4 5 -1 4

3

18
9 9 8 2 4 4 3 5 3 0 9 0 2 2 8 1 1 5

5

提示

【样例解释 #1】

只需要使用一次全局自增 $1$，即可得到 $a = [-4, -1, 1, 3, 4]$。此时，$\lvert a_1 \rvert, \lvert a_2 \rvert, \lvert a_3 \rvert, \lvert a_4 \rvert, \lvert a_5 \rvert$ 分别为 $4, 1, 1, 3, 4$，最大值为 $4$。可以证明 $4$ 是你能够取到的最小值。

【数据范围】

测试点编号	$n\le$	$\lvert a_i \rvert \le$	特殊性质
$1\sim 2$	$2$	$100$
$3\sim 4$	$3$	$500$
$5\sim 6$	$10$	$10^4$
$7\sim 8$	$30$	$10^6$
$9\sim 10$	$50$	$10^8$
$11\sim 12$	$100$	$5$
$13\sim 16$		$10^9$	A
$17\sim 18$			B
$19\sim 20$

• 特殊性质 A：保证 $n$ 为偶数，且对每个满足 $1 \leq k \leq \frac n2$ 的整数 $k$，$a_{2k-1} = -a_{2k}$。
• 特殊性质 B：保证 $a_i \geq 0$。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$-10^9 \leq a_i \leq 10^9$。