题目描述

​ 秋绘拥有 $n$ 张依次摆放的磁性卡牌，每张卡牌上有一个权值$ai$，每次她可以执行一个操作：选择任意一张仍存在的卡牌，让它相邻的一张卡牌加上（或减去）这张卡牌的权值，并删掉这张卡牌。显然，执行完 $n-1$ 次操作后，场上只会剩余一张卡牌。秋绘想最大化最后剩余的这张卡牌的权值，请你帮她找出这个最大权值。

​ 注意，每次操作你可以自由选择加或者减。相邻指的是位置上相邻，由于卡牌具有磁性，一张牌被删掉后，它后面的牌都会向前移动一个位置。

​ 例如：$n=4$，卡牌权值依次为$[1,2,3,4]$，当我们选择删掉这张权值为$3$牌，并且选择让它右边的卡牌加上它的权值，卡牌权值依次变为$[1,2,7]$，此时权值为$2$的卡牌和权值为$7$的卡牌相邻。

输入格式

第一行一个整数 $n$，代表卡牌数量。

第二行$n$个整数$a1,a2,...,an$，依次代表第$i$张卡牌上的权值。

输出格式

一个整数$K$，代表剩余一张牌时的最大权值。

样例

5 
1 2 3 4 5

15