问题描述

水羊羹是一种和菓子，主要由红豆糊倒入模具中，用寒天凝固而成。现在，JOI君手上有一块呈横长方体形状的水羊羹。JOI君计划把这块水羊羹作为今天的零食。

这块水羊羹上共有 $N-1$ 个纵向切口。水羊羹的长度是 $L_1 + L_2 + ... + L_N$，第 $i$ 个 $(1 ≤ i ≤ N-1)$ 切口位于从左边算起的位置 $L_1 + L_2 + ... + L_i$ 处。

这块水羊羹太大了，无法一口吃完，所以JOI君决定选择至少 $1$ 个切口，沿着选定的切口将水羊羹切开，分割成多个片段。然而，为了保持美观，片段的大小不能太不均匀，所以他决定尽量减小最大片段和最小片段的长度差。

请你求出最大片段和最小片段的长度差的最小值。

约束条件

• $2 ≤ N ≤ 50$
• $1 ≤ L_i ≤ 1000 (1 ≤ i ≤ N)$

输入

输入以以下格式从标准输入中给出。

$N$ $L_1$ $L_2$ : $L_N$

输出

输出最大片段和最小片段的长度差的最小值。

子任务 1 [10分]

• $N ≤ 15$

子任务 2 [27分]

• $L_i ≤ 10 (1 ≤ i ≤ N)$

子任务 3 [63分]

• 没有额外的限制。

输入示例 1

11
2
3
8
4
7
6
6
5
1
7
5

输出示例 1

2

在这个例子中，通过沿着第 $4$ 和第 $7$ 个切口切开，可以将水羊羹分成长度为 $17, 19, 18$ 的 $3$ 个片段。此时，最长的片段长度为 $19$，最短的片段长度为 $17$，所以长度差为 $2$ 。这是最小的长度差，因此输出为 $2$。

输入示例 2

2
1
10

输出示例 2

9

无论大小不均匀程度有多大，都必须选择至少 $1$ 个切口进行切割。

输入示例 3

5
5
5
5
5
5

输出示例 3

0

在这个例子中，可以将水羊羹刚好分割成 $5$ 个相同大小的片段。