Mizuyokan là một loại bánh ngọt Nhật Bản, được làm bằng cách đổ nhân chủ yếu từ đậu đỏ vào khuôn rồi dùng thạch agar để làm đông. JOI có một chiếc bánh mizuyokan hình hộp chữ nhật dài nằm ngang và định ăn chiếc bánh này trong bữa ăn nhẹ hôm nay.

Trên bánh có \(N-1\) vết khía theo chiều dọc để cắt. Chiều dài của bánh là \(L_1+L_2+\cdots+L_N\). Vết khía thứ \(i\) nằm ở vị trí cách đầu bên trái một khoảng \(L_1+L_2+\cdots+L_i\), với \(1 \le i \le N-1\).

Chiếc bánh quá lớn để ăn nguyên cả chiếc, nên JOI sẽ chọn ít nhất một vết khía và cắt theo các vết khía đã chọn để chia bánh thành nhiều miếng. Các miếng không đều nhau sẽ không đẹp mắt, vì vậy JOI muốn hiệu giữa chiều dài miếng dài nhất và chiều dài miếng ngắn nhất là nhỏ nhất có thể.

Hãy tìm giá trị nhỏ nhất của hiệu đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(L_i\).

Dữ liệu ra

In ra trên một dòng hiệu nhỏ nhất có thể giữa chiều dài miếng dài nhất và chiều dài miếng ngắn nhất.

Ràng buộc

• \(2 \le N \le 50\).
• \(1 \le L_i \le 1000\) với mọi \(1 \le i \le N\).

Phân nhóm

1. Nhóm 1 (10 điểm): \(N \le 15\).
2. Nhóm 2 (27 điểm): \(L_i \le 10\) với mọi \(1 \le i \le N\).
3. Nhóm 3 (63 điểm): Không có ràng buộc bổ sung.

Ví dụ

11
2
3
8
4
7
6
6
5
1
7
5

2

2
1
10

9

5
5
5
5
5
5

0

Nguồn

JOI 2017/2018, vòng loại, bài 4: Mizuyokan. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.