시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 8 | 7 | 6 | 100.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.
4 1 2 8 8
6
5 2 2 2 8 8
0
5 1 2 3 4 5
3