AT_joi2018_yo_d.水ようかん (Mizuyokan)

水羊羹是一种通过将主要由小豆构成的馅料倒入模具并用寒天凝固制成的日式甜点。现在，JOI 君拥有一块长方形的水羊羹，计划今天把它作为点心食用。

这块水羊羹上共分布了 $N-1$ 个竖直切口。水羊羹的总长度为 $L_1 + L_2 + \ldots + L_N$，其中，第 $i$ 个切口（$1 \leq i \leq N-1$）位于从左到右第 $L_1 + L_2 + \ldots + L_i$ 处。

由于整块水羊羹太大，JOI 君需要选择一些切口将水羊羹分成数块。为了美观，JOI 君想要使切分后的各块长度尽量一致，即最大块和最小块的长度差最小。

你的任务是计算出各块水羊羹中，最长的与最短的长度差的最小值。

输入如下：

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

输出一个整数，表示最长和最短水羊羹块的长度差的最小值。

• $2 \leq N \leq 50$
• $1 \leq L_i \leq 1000\ (1 \leq i \leq N)$

小任务 1 [10 分]

• $N \leq 15$

小任务 2 [27 分]

• $L_i \leq 10\ (1 \leq i \leq N)$

小任务 3 [63 分]

• 无任何附加限制

样例说明 1

在这个例子中，选择沿第 4 个和第 7 个切口切割，水羊羹被分成长 17、19 和 18 的三块。此时，最长的块为 19，最短为 17，所以长度差为 2。这是可能的最小值，因此输出 2。

样例说明 2

无论大小多么不均匀，都必须至少切一刀。

样例说明 3

在这个例子中，可以将水羊羹切成 5 块长度相同的块。

本翻译由 AI 自动生成