Trò chơi hai đầu (Deque)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có một deque gồm $N$ số nguyên. Hai người chơi lần lượt lấy phần tử ở đầu trái hoặc đầu phải, cho đến khi hết. Người thứ nhất tối đa hóa hiệu số tổng điểm của mình trừ tổng điểm người thứ hai; người thứ hai tối thiểu hóa hiệu số đó. Hãy tính hiệu số cuối cùng khi cả hai chơi tối ưu.

Input

Dòng đầu chứa $N$. Dòng hai chứa $N$ số nguyên.

Output

In hiệu số điểm của người thứ nhất trừ người thứ hai.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

4
10 80 90 30

Output

10

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.