Phòng máy tính của trường có ~n~ máy chủ chịu trách nhiệm xử lý một số tác vụ tính toán. Bạn biết số lượng nhiệm vụ đã lên lịch cho mỗi máy chủ: có ~m_i~ nhiệm vụ được giao cho máy chủ thứ ~i~.

Để cân bằng tải cho từng máy chủ, bạn muốn chỉ định lại một số nhiệm vụ để hiệu số nhiệm vụ giữa máy chủ tải nhiều nhất và máy chủ tải ít nhất là nhỏ nhất. Nói cách khác, bạn muốn biểu thức ~m_a - m_b~ là nhỏ nhất, trong đó ~a~ là máy chủ được tải nhiều nhất và ~b~ là máy chủ tải ít nhất.

Trong một giây, bạn chỉ có thể giao lại một nhiệm vụ. Vì vậy, trong một giây, bạn có thể chọn bất kỳ một cặp máy chủ nào và di chuyển một nhiệm vụ từ máy chủ này sang máy chủ còn lại.

Viết chương trình tìm số giây tối thiểu để cân bằng tải giữa các máy chủ.

Input

Dòng đầu tiên chứa số dương ~n~ ~(1 ≤ n ≤ 10^5)~ - số lượng máy chủ.

Dòng thứ hai chứa chuỗi các số nguyên không âm ~m_1, m_2, ..., m_n~ ~(0 ≤ m_i ≤ 2 \times 10^4)~, trong đó ~m_i~ là số tác vụ được giao cho máy chủ thứ ~i~.

Output

In số giây tối thiểu để cân bằng tải.

Sample 1

Input

2
1 6

Output

2

Sample 2

Input

7
10 11 10 11 10 11 11

Output

0

Sample 3

Input

5
1 2 3 4 5

Output

3

Giải thích

Ví dụ 1: Trong mỗi giây, một tác vụ từ máy chủ số ~2~ sẽ được chuyển sang máy chủ số ~1~. Sau hai giây, sẽ có ~3~ nhiệm vụ trên máy chủ số ~1~ và ~4~ tác vụ trên máy chủ số ~2~.

Ví dụ 2: Tải đã được cân bằng.

Ví dụ 3:

1. Chuyển một nhiệm vụ từ máy chủ số ~4~ sang máy chủ số ~1~ (dãy ~m~ trở thành: ~2~ ~2~ ~3~ ~3~ ~5~);
2. Chuyển một nhiệm vụ từ máy chủ số ~5~ sang máy chủ số ~1~ (dãy ~m~ trở thành: ~3~ ~2~ ~3~ ~3~ ~4~);
3. Chuyển một nhiệm vụ từ máy chủ số ~5~ sang máy chủ số ~2~ (dãy ~m~ trở thành: ~3~ ~3~ ~3~ ~3~ ~3~).

Trình tự trên là một trong số các cách khả thi để cân bằng tải của các máy chủ trong ba giây.