Có một dãy gồm \(N\) đồng xu được đặt trên bàn, mỗi đồng xu có giá trị nguyên \(a_i\). An và Bình chơi một trò chơi như sau: mỗi lượt, người chơi nhặt một đồng xu ở một trong hai đầu dãy (đầu trái hoặc đầu phải) và bỏ vào túi của mình. Sau \(N\) lượt, tất cả đồng xu đều được nhặt hết. Người nào có tổng giá trị xu lớn hơn sẽ thắng. Nếu hòa, Bình thắng (vì là người đi sau). An đi trước. Cả hai đều chơi tối ưu.

Hãy xác định tổng giá trị lớn nhất mà An có thể đạt được khi cả hai chơi tối ưu.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 100\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^3\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng giá trị lớn nhất An có thể đạt được.

Ví dụ

Input:

5
3 7 2 5 4

Output:

11

Ràng buộc