背景

建议先看 B 题题目背景。

题目描述

有一个初始长度为 $n$ 的序列 $a$。你需要进行 $n-1$ 次操作。每一次操作先在当前序列中选出两个相邻的数 $x,y$ 并删除（原序列中 $x$ 在 $y$ 左边），再往原位置插入一个 $x+y$ 或一个 $x-y$。$n-1$ 次操作之后最终只会剩下恰好一个数，求这个剩下的数的最大值。

输入格式

第一行，一个整数 $n$。

第二行，共 $n$ 个整数 $i$ 个表示 $a_i$。

输出格式

共一行，一个整数，表示答案。

5
-1 1 1 -1 1

3

提示

对于 $100\%$ 的数据，$1\le n\le 10^5,|a_i|\le 10^9$。

样例解释

一种操作过程如下：

-1 1 1 -1 1

-1 1 1 -2

-1 1 3

-1 4

3

可以证明没有更优的方案。