23703번 - Anatoly Shalyto 다국어

문제

Median of a multiset of integers is the smallest integer $X$ such that at least half of the elements of the set are less than or equal to $X$.

Mode of a multiset of integers is the value that occurs the most times in the multiset. If there are multiple such values the mode is the smallest.

Imbalance of a multiset is the absolute difference between the median and the mode.

A multiset $T$ is a subset of a multiset $S$ if for every value the number of its occurrences in $S$ isn't less than the number of its occurrences in $T$.

You are given a multiset of integers. Consider its non-empty subset with the largest imbalance. Print that imbalance.

입력

The first line contains a single integer $n$ (1ドル \leq n \leq 10^5$), size of the multiset.

The second line contains $n$ integers $a_i$ (0ドル \leq a_i < 10^9, a_i \leq a_{i+1},ドル elements of the multiset.

출력

Print a single integer --- the largest imbalance of some subset of the given multiset.

제한

힌트