C-小苯的数字合并_牛客小白月赛94

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

大白熊给了小苯一个长度为 $n$ 的数组 $a$ ，小苯想要最大化 $a$ 的极差。

具体的，小苯可以做如下操作任意次（前提是数组至少有两个数字）：

$\bullet$ 选择一个正整数 $i \ (1 \leq i <n)$ ，接着将 $a_i$ 与 $a_{i+1}$ 合并为一个数字，结果为二者的和。

（即：将 $a_i$ 变为 $a_i + a_{i+1}$ ，然后删去 $a_{i+1}$ ，当然操作完后 $a$ 的长度也会减一。）

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

输入包含两行。
第一行一个正整数 ，表示数组  的长度。
第二行  个正整数 ，表示初始时数组  的元素。

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

示例1

复制

4
3 2 2 3

复制

一种可能的操作方式是：
选择将  合并，数组此时变为。
然后再选择  合并，数组此时变为 ，极差为 。
可以证明不存在比  更大的极差。

数组的极差定义为：数组中的最大值和最小值的差。