index.md

吉良吉影想平靜地過日子

\begin{figure}[h] \centering \includegraphics[width=12cm]{kira2.jpg} \caption{「在你告訴別人之前，我要先把你收拾掉，讓我今晚也能好好睡一覺。」 \出自動畫《JoJo的奇妙冒險·第四部·不滅鑽石》} \end{figure}

杜王町存在一位名為 \underline{吉良} 的危險人物。在他遭遇到 \underline{重清} 識破他的身分時，他決定使用他的特殊能力「殺手皇后」消滅對方，因而與重清的「收成者」對峙。 「收成者」有如一群蟲子，他們會一擁而上攻擊目標敵人；吉良的能力「殺手皇后」可以將任何物體變為炸彈，而他決定將一隻隻「收成者」變成炸彈，再引發爆炸消滅他們。

雖然「收成者」會一擁而上，但因為秩序零落、完全不同步，吉良將他們視為一隻隻依序攻擊。 吉良會持續引爆多隻「收成者」：他會依序選擇最少一隻、最多全部首先湧上的前幾隻一次引爆，未被引爆的再重複選擇前幾隻、一次引爆，並一次次重複選擇、引爆，直到全部「收成者」都被引爆而消滅殆盡。 不過，在每次選擇之前，他必須先考慮爆炸的強度與範圍。

每隻「收成者」都有自己的耐久度 $w_i$，而爆炸的強度也隨之影響：當吉良選擇引爆一群「收成者」時，引爆的強度必須恰好為該群「收成者」的耐久度總和（畢竟過強會炸傷自己、過弱又不能確實消滅對手）。 雖然吉良每次都可以製造任意強度的爆炸，但是因為有著完美一致性的強迫症，所以他限制自己每次爆炸的強度都必須相同。

而爆炸的範圍等同於引爆的「收成者」的數量。 吉良可以一次引爆所有「收成者」，但是範圍越大就越容易被旁人發現，因此他希望所有爆炸中範圍最大的那次爆炸範圍越小越好。

你的任務是替吉良找出最小的範圍 $k$，使他有辦法在接連爆炸下消滅所有「收成者」，且每次爆炸的強度相同、整體範圍在 $k$ 以下。

\clearpage

輸入

第一行有一個數字 $n$，代表收成者的數目。
第二行有 $n$ 個數字，依序代表湧上的「收成者」的耐久度 $w_i$。

輸出

輸出最小的範圍 $k$。

輸入限制

• $1 \leq n \leq 8000$
• $1 \leq w_i \leq 10^9$

子任務

\subtasks

\clearpage

範例輸入 1

5
1 2 2 1 3

範例輸出 1

2

範例說明 1

吉良引爆了$3$次，每次引爆的「收成者」的耐久度依序為 $\langle 1, 2\rangle$, $\langle 2, 1\rangle$, $\langle 3\rangle$。爆炸強度為 $3$，需要 $2$ 單位爆炸範圍。

範例輸入 2

9
8 3 3 5 2 1 5 3 3

範例輸出 2

4

範例說明 2

吉良引爆了$3$次，每次引爆的「收成者」的耐久度依序為 $\langle 8, 3\rangle$, $\langle 3, 5, 2, 1\rangle$, $\langle 5, 3, 3\rangle$。爆炸強度為 $11$，需要 $4$ 單位爆炸範圍。

範例輸入 3

5
1 2 4 8 16

範例輸出 3

5

範例說明 3

吉良引爆了$1$次，引爆的「收成者」的耐久度依序為 $\langle 1, 2, 4, 8, 16\rangle$。爆炸強度為 $31$，需要 $5$ 單位爆炸範圍。

\clearpage

範例輸入 4

7
999999999 999999999 999999999 999999998 999999997 999999996 6

範例輸出 4

4

範例說明 4

吉良引爆了$2$次，每次引爆的「收成者」的耐久度依序為 $\langle 999999999, 999999999, 999999999\rangle$,
$\langle 999999998, 999999997, 999999996, 6\rangle$。爆炸強度為 $2999999997$，需要 $4$ 單位爆炸範圍。