题目内容

曾经有一位叫做小红的小伙子，他是一位有着非常高超数学技能的年轻人，对于算术和几何学方面非常着迷。有一天，他得到了一个由 $n$ 个整数构成的数组。但是他很快发现这个数组非常不平衡，有些元素太大而有些元素太小，于是他想进行一次操作，使得数组变得更加平衡。

他的操作非常简单：他可以选择两个相邻的元素，将它们合并成一个元素，新元素的值等于原来两个元素的和。但是他只能进行一次这样的操作。

他决定利用他的数学技能，找到可以让数组变得最平衡的方法。

他定义数组的极差为数组的最大值减去最小值。他的目标是使得操作后数组的极差尽可能的小，你能帮小红解决吗？

输入描述

输入第一行为一个整数 $n$ ，表示数组的长度。

输入第二行为 $n$ 个整数，第 $i$ 个整数为 $a_i$ 。

$2\le n \le 10^5$， $1\le a_i \le 10^9$

输出描述

一个整数，代表操作后的极差最小值。

样例

输入

3
1 4 5

输出

0

思路:枚举 + 前缀优化

step1:暴力枚举

考虑枚举每个$i \in [1 , n - 1]$ . 相加然后整体求解最大值最小值。这样复杂度为$O(n^2)$.