15945번 - Make Similar

문제

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

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

입력

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

두 번째 줄에 공백을 사이에 주고 n개의 정수 A₁, …, A_n (-10⁹ ≤ A_i ≤ 10⁹)이 주어진다.

출력

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

제한

힌트

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