시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 512 MB 101 40 34 45.333%

문제

n개의 정수로 이루어진 수열 A1, A2, …, An이 있다. 당신은 이 수들을 최대한 비슷하게 만들고자 한다.

당신은 이 수열에서 두 수를 골라 둘 중 하나를 다른 하나에 더하는 작업을 여러 번 수행할 수 있다. 작업을 하고 싶은 만큼 수행하여 n개의 수 중 최댓값과 최솟값의 차이를 최소로 만들려고 한다. 이 때, 그 차이를 구하여라.

입력

첫 번째 줄에 수열의 길이 n(1 ≤ n ≤ 105)이 주어진다.

두 번째 줄에 공백을 사이에 주고 n개의 정수 A1, …, An (-109 ≤ Ai ≤ 109)이 주어진다.

출력

첫 번째 줄에 max(A1, ..., An) - min(A1, ..., An)의 가능한 최솟값을 출력한다.

예제 입력 1

3
1 2 3

예제 출력 1

1

힌트

A1 += A2 를 수행하면 [3, 2, 3]이 되어 최댓값 - 최솟값이 1이 된다.