题目描述

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

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

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

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

输入描述

输入第一行为一个整数$n(2\le n\le 10^5)$ ，表示数组的长度。

输入第二行为$n$个整数，第 $i$ 个整数为$a_i(1\le a_i\le 10^9)$ 。

输出描述

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

样例

输入

3
1 4 5

输出

0