一个整数多重集的中位数是满足以下条件的最小整数 $X$：该集合中至少有一半的元素小于或等于 $X$。

一个整数多重集的众数是在该多重集中出现次数最多的值。如果存在多个这样的值，则众数为其中最小的一个。

一个多重集的不平衡度是其中位数与众数之差的绝对值。

如果对于任意数值，其在多重集 $S$ 中的出现次数都不小于在多重集 $T$ 中的出现次数，则称多重集 $T$ 是多重集 $S$ 的子集。

给你一个整数多重集。考虑其所有非空子集中不平衡度最大的一者。输出该最大不平衡度。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示多重集的大小。

第二行包含 $n$ 个整数 $a_i$（$0 \le a_i < 10^9$，$a_i \le a_{i+1}$），表示多重集中的元素。

输出格式

输出一个整数，表示该给定多重集的某个非空子集的最大不平衡度。

样例

输入样例 1

4
1 2 8 8

输出样例 1

6

输入样例 2

5
2 2 2 8 8

输出样例 2

0

输入样例 3

5
1 2 3 4 5

输出样例 3

3