题目描述

小玮和 Kitten 正在玩一款游戏。游戏中有 $n$个城市，从左到右编号从 $1 \sim n$，编号为 $i$的城市有 $a_{i}$的资源。

小瑞一开始在城市 $1$，Kitten 一开始在城市 $n$。

游戏轮流进行，小瑞先操作，Kitten 后操作。两人所在城市相邻时游戏结束。

假设小瑞在城市 $i$。轮到他操作时有两种操作方法：他可以选择可以走到城市 $i+1$；或者如果 Kitten 不在城市 $i+2$，就可以绕过城市 $i+1$，暗渡走到 $i+2$。

假设 Kitten 在城市 $i$。轮到她操作时有两种操作方法：她可以选择可以走到城市 $i-1$；或者如果小瑞不在城市 $i-2$，就可以绕过城市 $i-1$，暗渡走到 $i-2$。

游戏最终的评分为小瑞走到的所有城市的资源值之和减去Kitten 走到的所有城市的资源值之和的数值。

小瑞的游戏目标为最大化最终评分，Kitten 的目标为最小化最终评分。

假设两个人都足够聪明，请你输出最终评分会是多少。

输入格式

第一行为一个数 $n$。

第二行为 $n$个整数 $a_{1} \sim a_{n}$。

输出格式

一个整数，即最终评分。

输入 #1

2 1 3

输出 #1

-2

输入 #2

4 2 2 2 2

输出 #2

2

输入 #3

4 2 6 2 2

输出 #3

4

4
787777064 884380032 679044648 847794339

619027373

4
252924428 879820086 866389265 698748455

420565238

4
123047628 244291628 726539568 908413437

-58826241

说明/提示

数据范围

对于 $100\%$的数据，$2 \le n \le 5 \times 10^{3}$，$1 \le a_{i} \le 10^{9}$。

子任务 $1$（$10$分）：保证 $n = 4$。

子任务 $2$（$20$分）：保证 $a_{i} = 33$。

子任务 $3$（$30$分）：保证 $n = 20$。

子任务 $4$（$40$分）：没有特殊限制。