시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB333100.000%

문제

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.

예제 입력 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