비슷하게 만들기

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

요약

정수 n개가 주어질 때, 한 원소를 다른 원소에 더하는 연산을 반복해 최댓값과 최솟값의 차이를 가장 작게 만드는 값을 구합니다.

문제

정수 $n$ 개로 이루어진 수열 $A_1, A_2, \ldots, A_n$ 이 있다. 당신은 이 수들을 최대한 비슷하게 만들고자 한다.

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

첫 번째 줄에 수열의 길이 $n$ ( $1 \le n \le 10^5$ )이 주어진다.

두 번째 줄에 공백으로 구분된 정수 $n$ 개 $A_1, \ldots, A_n$ ( $-10^9 \le A_i \le 10^9$ )이 주어진다.

첫 번째 줄에 $\max(A_1, \ldots, A_n) - \min(A_1, \ldots, A_n)$ 의 가능한 최솟값을 출력한다.

$A_1 += A_2$ 를 수행하면 [3, 2, 3]이 되어 최댓값과 최솟값의 차이가 1이 된다.