Lấy số từ hai đầu mảng

Hai người chơi \(A\) và \(B\) cùng chơi trên một mảng gồm \(n\) số nguyên (có thể âm). Họ lần lượt đi, \(A\) đi trước. Ở mỗi lượt, người chơi chọn một trong hai đầu của mảng rồi lấy đi một hoặc nhiều số liên tiếp tính từ đầu đó (số lượng tuỳ ý, ít nhất là \(1\), nhưng chỉ lấy từ một đầu trong một lượt). Điểm của mỗi người là tổng các số mà người đó đã lấy. Trò chơi kết thúc khi mảng hết số.

Mỗi người đều chơi tối ưu để điểm của mình hơn điểm đối phương càng nhiều càng tốt. Hãy cho biết hiệu số (điểm của \(A\)) trừ (điểm của \(B\)) khi kết thúc.

Input

Dữ liệu gồm nhiều bộ test, mỗi bộ gồm hai dòng: số \(n\) rồi \(n\) số nguyên của mảng. Dữ liệu kết thúc bằng một dòng chứa \(n = 0\) (dòng này không phải là bộ test).

Output

Với mỗi bộ test, in ra trên một dòng hiệu số điểm lớn nhất mà người đi trước có thể đạt được so với người đi sau.

Constraints

• \(1 \le n \le 100\)
• \(|a_i| \le 1000\)
• Có không quá \(300\) bộ test trong một tệp.

Sample Input

5
3 -1 5 -4 2
3
-5 10 -5
0

Sample Output

5
10

Explanation

Ở bộ thứ hai, \(A\) lấy hai số \(-5, 10\) từ đầu trái được \(5\) điểm, \(B\) buộc phải lấy số \(-5\) còn lại. Hiệu số là \(5 - (-5) = 10\).