题目背景

总所周知！王赞博有了女朋友却谁也不知道。但是王赞博有“暗恋”对象，于是就被王赞博的女朋友给知道了，但是呢，王赞博的女朋友是一个热爱画画的温柔又可爱的女孩纸，于是她决定把王赞博大卸两块，没错是两块！！

题目描述

王赞博呢，他的长度为 n，并且每个单位长度都有一个相对应的重量，他的小女朋友希望将王赞博切成两部分后，两个部分中的最大重量之差的绝对值最大（显然两个部分均不能为空啊），她呢觉得很惆怅，不知道该怎么切最好，所以想让在座的各位大佬来想想办法。

输入输出格式

输入格式：

第一行为一个n（2 <= n <= 1e5），表示王赞博的长度，第二行为n个数，表示王赞博每个单位长度的重量（0 <= a[i] <= 1e6）。

输出格式：

输出切成两部分后，每部分的重量的最大值之差的绝对值最大是多少。

输入输出样例

输入样例1：

4
1 2 3 4

输出样例1：

3

说明

对于样例：

4

1 2 3 4

那么一共有 3 种切法，分别是：

第一部分为 { 1 }， 第二部分为{ 2，3，4 }，此时两部分的最大值之差的绝对值为 3

第一部分为 { 1，2 }， 第二部分为{ 3， 4 }，此时两部分的最大值之差的绝对值为 2

第一部分为 { 1，2，3 }， 第二部分为{ 4 }，此时两部分的最大值之差的绝对值为 1

所以答案为3.