思路:枚举 + 前缀优化

step1:暴力枚举

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

题目内容

小 A 得到了一个由 $n$ 个正整数构成的序列，他希望让数据整体上更平稳一些。他可以执行一次“相邻融合”操作：选择序列中相邻的两个元素，将它们合并为一个元素，新元素的值等于这两个元素之和。

定义序列的“波动幅度”为序列中最大值与最小值之差。小 A 的目标是，在执行恰好一次相邻融合后，让新序列的波动幅度尽可能小。

约束条件：

• 元素个数 $n$ 满足 $2 \le n \le 10^5$。
• 每个元素的值 $x_i$ 满足 $1 \le x_i \le 10^9$。

输入描述

第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个整数，依次表示初始序列的各个元素，相邻整数之间用空格分隔。

输出描述

输出一个整数，表示操作后波动幅度的最小值。

样例1

输入

4
1 2 3 4

输出

1

说明

序列初始为 1 2 3 4，长度 $n=4$。 尝试所有相邻融合：

• 合并第 1 和 2 个元素（1 和 2）得到 3，新序列为 3 3 4，最大值 4，最小值 3，波动幅度为 $4 - 3 = 1$。
• 合并 2 和 3 得 5，序列 1 5 4，最大 5 最小 1，差 $4$。
• 合并 3 和 4 得 7，序列 1 2 7，差 $6$。 最小波动幅度为 1。

样例2

输入

5
10 20 30 40 50

输出

20

说明

序列为 10 20 30 40 50，$n=5$。 枚举合并：

• 合并前两个得到 30，序列 30 30 40 50，波动幅度 $50-30=20$。
• 合并第 2、3 个得 50，序列 10 50 40 50，幅度 $50-10=40$。
• 合并 3、4 得 70，序列 10 20 70 50，幅度 $70-10=60$。
• 合并 4、5 得 90，序列 10 20 30 90，幅度 $90-10=80$。 最小值为 20。

样例3

输入

2
1 5

输出

0

说明

序列只有两个元素 1 和 5。 进行唯一一次相邻融合操作后，序列变为只包含一个元素 6。 此时序列中最大值与最小值均为 6，波动幅度为 $0$。

样例4

输入

6
5 9 2 8 3 7

输出

7

说明

序列 5 9 2 8 3 7。枚举五种合并方式，计算每次新序列的波动幅度：

• 合并 5 和 9 得 14，序列 14 2 8 3 7，最大值 14，最小值 2，幅度 $12$。
• 合并 9 和 2 得 11，序列 5 11 8 3 7，幅度 $11-3=8$。
• 合并 2 和 8 得 10，序列 5 9 10 3 7，幅度 $10-3=7$。
• 合并 8 和 3 得 11，序列 5 9 2 11 7，幅度 $11-2=9$。
• 合并 3 和 7 得 10，序列 5 9 2 8 10，幅度 $10-2=8$。 最小波动幅度为 7。