Đề bài

Egg Lupin là một tên trộm khét tiếng, nổi danh trong lĩnh vực phá khóa. Để chứng minh mình là bậc thầy thực sự, hắn phải vượt qua thử thách phá khóa của thám tử lừng danh Sherlock Yugi.

Trên một tờ giấy, Yugi viết một dãy số. Nhiệm vụ của Egg (và bạn) là:

• Với mọi giá trị \(X\) bất kỳ, chia dãy số thành hai phần không rỗng:
  • Nhóm 1: gồm các phần tử có giá trị không lớn hơn \(X\)
  • Nhóm 2: gồm các phần tử có giá trị lớn hơn \(X\)
• Với các cách chọn \(X\) hợp lệ, tính độ chênh lệch nhỏ nhất có thể giữa tổng hai nhóm

Yêu cầu: Tìm độ chênh lệch nhỏ nhất giữa tổng hai nhóm sau khi chia dãy theo quy tắc trên.

Dữ liệu vào

• Dòng đầu tiên là số nguyên dương \(n\) — số phần tử trong dãy (\(2 \leq n \leq 10^6\))
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^9\))

Đảm bảo dãy có ít nhất 2 số khác nhau.

Dữ liệu ra

• In ra một số nguyên duy nhất — độ chênh lệch nhỏ nhất giữa tổng hai nhóm sau khi chia

Sample Input 1

3
1 2 3

Sample Output 1

0

Sample Input 2

4
1 3 1 1

Sample Output 2

0

Sample Input 3

6
3 1 1 5 1 5

Sample Output 3

4

Giải thích

Test 1:

• Chọn \(X = 2\), dãy chia thành {1, 2} và {3}
• Tổng hai nhóm đều là 3, nên chênh lệch là \(|3 - 3| = 0\)

Test 2:

• Chọn \(X = 2\), chia thành {1, 1, 1} và {3}, tổng lần lượt là 3 và 3 → chênh lệch là 0

Test 3:

• Chọn \(X = 4\), chia thành {3, 1, 1, 1} và {5, 5}, tổng lần lượt là 6 và 10 → chênh lệch là 4