Another

题目描述

给定一个长为 $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$ 的最小值。

输入输出样例 #1

输入 #1

5
-5 -2 0 2 3

输出 #1

4

输入输出样例 #2

输入 #2

6
1 -1 4 5 -1 4

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

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$ 是你能够取到的最小值。

【数据范围】

• 特殊性质 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$。