P11797 【MX-X9-T1】『GROI-R3』Another Me

一股巨大的斥力袭来。全身上下仿佛分裂成了透明的碎片。 镜中有一个模糊的人影。是「你」吗？还是仅仅来源于幻觉？无从知道。你想要向前走，可对方却保持着极端的默契向后退去。当你让步时，对方却又赶了上来。 已经没有任何能量支撑你接着思考下去了。但朝着棱镜中央那丝微弱的光源，*你无论如何都想要再靠近一点*。此外，还有对面的另一个「你」......

给定一个长为 $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$ 的绝对值。你只需要计算这个最小化后的结果即可。

无

无

**【样例解释 #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$ | $100$ | $10^9$ | A | | $17\sim 18$ | $100$ | $10^9$ | B | | $19\sim 20$ | $100$ | $10^9$ | | - 特殊性质 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$。