题目描述

给定一个长度为 $n$ 的序列 $A$，你需要划分这个序列。先任意选择若干个位置，假定你选择了 $m$ 个位置，这些位置分别为 $B_1,B_2...B_m$ ，这一次划分的代价为下面两个量中的最大值：

• $\sum\limits_{i=1}^{m}A_{B_{i}}$ .
• $\max\limits_{i=0}^{m}{\large{\sum\limits_{j=B_i+1}^{B_{i+1}-1}}{A_j}}$ 。 特别的，定义$B_0=0,B_{m+1}=n+1$，同时，若 $B_i=B_{i+1}$ ，则在原式中 $\sum$ 一项的值你应当视为 0。

即为：你选择了若干位置，这些位置将原序列分隔成了若干段。代价是你选择的这些位置的元素和与每一段中所有的元素和的最大值。

给定 $n$ 与序列 $A$ ，求最小分隔代价。

输入格式

第一行输入$n$。

第二行输入$n$个数字$A_1,...,A_n$。

输出格式

一个数字表示答案。

样例输入 #1

6
1 4 5 3 3 2

样例输出 #1

7

样例输入 #2

5
1 2 3 4 5

样例输出 #2

5

样例输入 #3

6
4 1 6 3 10 7

样例输出 #3

11

数据范围

对于20%的数据：保证$n\leq 20$。

对于60%的数据：保证$n\leq 1000$。

对于100%的数据：保证$1\leq n \leq 10^5,1\leq a_i\leq 10^9$。