题目描述

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

• 全局自增 $1$：对每个 $1 \le i \le n$，将 $a_i$ 自增 $1$；
• 全局自减 $1$：对每个 $1 \le i \le 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

提示

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