Anatoly Shalyto

시간 제한2초메모리 제한512 MB

요약

정렬된 중복집합이 주어질 때, 모든 비어 있지 않은 부분 중복집합 중 중앙값과 최빈값 차이의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 정렬, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1
입력
```
4
1 2 8 8
```
예상 출력
```
6
```
예제 2
입력
```
5
2 2 2 8 8
```
예상 출력
```
0
```
예제 3
입력
```
5
1 2 3 4 5
```
예상 출력
```
3
```