Giải bài trực tuyến

       Tiền bạc vẫn luôn là thứ có giá trị đối với mỗi con người, kể cả với pirate. Vì vậy, khi hòn đảo xinh đẹp của tên cướp biển khét tiếng này sắp bị... giải tỏa, hắn đã tranh thủ vơ vét cho đến đồng tiền vàng cuối cùng. Trên hòn đảo có N mỏ vàng nằm cạnh nhau trên một đường thẳng, đánh số từ 1 đến N. Mỏ vàng i có giá trị là p_i. Đội thi công sẽ có nhiệm vụ san lấp hết N mỏ vàng này. Nhưng tại mỗi thời điểm, pirate cố gắng ngăn cản việc san lấp bằng cách xây một bức tường ngăn cách hai mỏ vàng liên tiếp nào đó, vậy là cụm mỏ còn lại được chia làm 2 phần. Đội thi công sẽ chọn một trong hai phần đó để san lấp hết, thế là pirate giữ lại được phần còn lại và hắn sẽ nhận được số đồng tiền vàng đúng bằng tổng giá trị của những mỏ còn lại đó. Công việc cứ tiếp tục cho đến khi chỉ còn lại một mỏ vàng duy nhất. Đội thi công biết điều đó, cho nên họ đã có chiến thuật san lấp để cực tiểu hóa số tiền của pirate. Với lòng tham không đáy, pirate quyết tâm lấy càng nhiều vàng càng tốt. Hãy giúp con người khốn khổ vì tiền này !

Input

Dữ liệu vào gồm nhiều dòng:

• Dòng 1: Một số nguyên dương N (1 ≤ n ≤ 2000).
• Dòng 2...n+1: Mỗi dòng ghi giá trị p_i của từng mỏ vàng theo thứ tự từ 1 đến n (1 ≤ p_i ≤ 1000).

Output

Dữ liệu ra gồm 1 dòng duy nhất ghi ra số đồng tiền vàng lớn nhất có thể vơ vét được.

Example

Input:
5
8
6
2
4
2

Output:10

Giải thích: Đầu tiền pirate chia mỏ vàng thành 2 phần [1,2] và [3,4,5]. Xe ủi sẽ san lấp phần [1,2] và pirate nhận được p_2 + p_3 + p_4 = 8 đồng tiền vàng. Tiếp theo chia [3,4,5] thành [3] và [4,5]. Xe ủi san lấp [4,5] và pirate thu thêm p_2 = 2 đồng tiền vàng. Công việc kết thúc vì chỉ còn 1 mỏ, vậy tổng cộng thu được là 8 + 2 = 10 đồng tiền vàng. Không có cách nào giúp hắn thu thêm tiền.