相邻删除

时间限制：2s
空间限制：1024MB

题目描述

给定长度为 $N$ 的数列 $A$。不断选择相邻两个数并将它们同时删除，直到序列长度不超过 1；每次得分是所删两数之差的绝对值。求可能得到的最大总分。

输入格式

第一行一个整数 $N$，第二行 $N$ 个整数 $A_1,\ldots,A_N$。

输出格式

输出最大总分。

样例输入 1

4
1 2 5 3

样例输出 1

5

样例输入 2

7
3 1 4 1 5 9 2

样例输出 2

14

数据范围

对于所有数据，$2\le N\le3\times10^5$，$1\le A_i\le10^9$。