Page not loading? Try clicking here.
Placeholder

#5445
Subtask

공평하게 나누자 1s 32MB

Problems

N명의 사람이 각각 C_i원의 금액을 보유하고 있다.

서로 가진 금액을 교환하여 모두가 가진 금액의 차이가 0 혹은 1이 되게 하기 위해 움직여야 하는 최소 금액을 출력하시오.


Input

첫 번째 줄에 N이 입력된다(1 ≤ N ≤ 100,000).

두 번째 줄에 C_1, C_2 ... C_N가  입력된다. (1 ≤​ C_i ≤​ 1,000)


Output

서로 가진 금액을 교환하여 모두가 가진 금액의 차이가 0 혹은 1이 되게 하기 위해 움직여야 하는 최소 금액을 출력한다.


Example 

6

3 8 5 4 2 1
5

총 3 + 8 + 5 + 4 + 2 + 1 = 23 원을 모두가 공평하게 나눠 갖기 위해서는 C_2가 C_5에게 1원, 그리고 C_6에게 3원을 주고, C_3가 C_5에게 1원을 주면 된다.



Source

JUNGOL - klee

You must sign in to write code.