该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

本题需要使用文件输入输出，文件名为 num.in 和 num.out。

小田的数字合并

题目描述

小田又得到了一个长度为 $n$ 的数组 $a$，他这次想要最大化 $a$ 的极差。

小田可以对数组做如下操作任意次（前提是数组中至少有两个数字）：

• 选择一个正整数 $i(1 \le i \lt n)$，接着将 $a_i$ 和 $a_{i+1}$ 合并为一个数字，结果为两者的和。（即：将 $a_i$ 变为 $a_{i} + a_{i+1}$，然后删除 $a_{i+1}$，当然操作完后 $a$ 的长度也会减一。）

小田想知道他最大能将数组极差变为多少呢，请你帮帮他吧！

说明：极差指数组中最大值和最小值之差。

输入描述

输入包含两行。

第一行一个正整数 $n$，表示数组 $a$ 的长度。

第二行 $n$ 的正整数 $a_{i}$，表示数组 $a$ 的元素。

输出描述

输出包含一行一个整数，表示小田操作完后，数组 $a$ 的最大极差。

输入输出样例

输入 #1

4
3 2 2 3

输出 #1

4

输入 #2

5
2 1 3 2 4

输出 #2

8

说明/提示

【样例 1 解释】

合并 $a_{2}, a_{3}, a_{4}$，数组变为 $[3, 7]$，极差为 $4$ 。

另一种方案是合并 $a_{1}, a_{2}, a_{3}$，结果一样。

【样例 2 解释】

合并 $a_{3}, a_{4}, a_{5}$，数组变为 $[2, 1, 9]$，极差为 $8$ 。

【数据范围】

对于 $10 \%$ 的数据，有：$n = 3$ 。

对于另外 $10\%$ 的数据，有：$a_i$ 呈升序排列。

对于所有测试数据，有：$1 \le n \le 2 \times 10^{5}, 1 \le a_{i} \le 10^9$ 。