Taro và Jiro chơi với nhau một trò chơi như sau:

Cho tập hợp gồm ~N~ số nguyên dương ~a=(a_1,a_2,...,a_N)~. Hai người chơi sẽ lần lượt thực hiện các nước đi sau đến khi ~a~ rỗng, với Taro là người bắt đầu:

• Loại bỏ phần tử đầu tiên hoặc cuối cùng của dãy ~a~. Người chơi đó sẽ kiếm được ~x~ điểm, với ~x~ là phần tử bị loại bỏ.

Cho ~X~ và ~Y~ lần lượt là số điểm của Taro và Jiro sau khi trò chơi kết thúc. Taro muốn ~X - Y~ lớn nhất có thể, trong Jiro lại muốn làm ~X - Y~ bé nhất có thể.

Giả sử cả hai người đều chơi tối ưu, tìm giá trị của ~X - Y~.

Input:

• Dòng thứ nhất chứa hai số nguyên dương ~N (1 \leq N \leq 3000)~.
• Dòng thứ hai chứa ~N~ số nguyên dương thỏa mãn ~a_1, a_2, a_3, ..., a_N (1 \leq a_i \leq 10^9)~.

Output:

• In ra giá trị ~X - Y~ cần tìm.

Sample 1

Input

4
10 80 90 30

Output

10

Giải thích

Trò chơi diễn ra như sau nếu hai người đều chơi tối ưu (với phần tử được in đậm là phần tử được chọn):

• Taro: (10, 80, 90, 30) → (10, 80, 90)
• Jiro: (10, 80, 90) → (10, 80)
• Taro: (10, 80) → (10)
• Jiro: (10) → ()

Ở đây, ~X = 30 + 80 = 110~ và ~Y = 90 + 10 = 100~.

Sample 2

Input

3
10 100 10

Output

-80

Giải thích:

Trò chơi diễn ra như sau nếu hai người đều chơi tối ưu (với phần tử được in đậm là phần tử được chọn):

• Taro: (10, 100, 10) → (100, 10)
• Jiro: (100, 10) → (10)
• Taro: (10) → ()

Ở đây, ~X=10+10=20~ và ~Y=100~.

Sample 3

Input

1
10

Output

10

Sample 4

Input

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

Output

4999999995

Sample 5

Input

6
4 2 9 7 1 5

Output

2

Giải thích:

Trò chơi diễn ra như sau nếu hai người đều chơi tối ưu (với phần tử được in đậm là phần tử được chọn):

• Taro: (4, 2, 9, 7, 1, 5) → (4, 2, 9, 7, 1)
• Jiro: (4, 2, 9, 7, 1) → (2, 9, 7, 1)
• Taro: (2, 9, 7, 1) → (2, 9, 7)
• Jiro: (2, 9, 7) → (2, 9)
• Taro: (2, 9) → (2)
• Jiro: (2) → ()

Ở đây, ~X=5+1+9=15~ và ~Y=4+7+2=13~.