You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

T3 蛋糕（cake）

题目描述

你现在得到了一个二维蛋糕，它从左到右可以分成 $n$ 列，每列高为 $a_i$。对于每一列，又可以从下到上分为 $a_i$ 块，并且最上面一块权值为 $1$，从上到下权值依次加 $1$。每一列的最上面的权值为 $1$ 的块的上表面有“奶油”。

你现在要把这一个蛋糕分成若干个矩形，要求每一个矩形上都要有“奶油”，也即每个矩形要包含至少一个权值为 $1$ 的块。显然蛋糕中的每一格都必须被划分到恰好一个矩形内，且矩形不能包含没有蛋糕的格子。

定义每一块矩形的代价为其每一行的最大值之和，即 $\sum\limits_{i=l}^r(\max\limits_{j=d}^u v_{i,j})$。特别地，对于宽（列数）为 $1$ 的矩形，代价为矩形内权值的最大值。请你最小化划分整个蛋糕的代价。

输入格式

第一行一个整数 $n$ 表示序列长度。

第二行 $n$ 个整数 $a_i$ 表示序列。

输出格式

一行一个整数表示答案。

样例1

样例输入

5
5 1 4 3 2

样例输出

15

样例解释

全部竖着删即可，代价 $5+1+4+3+2$

样例2

样例输入

5
4 5 4 5 4

样例输出

16

样例解释

全部横着删即可，代价 $5+4+3+2+1+1$

样例3

样例输入

10
1 1 1 1 10 1 1 1 1 1

样例输出

12

样例4

样例输入

10
12 12 21 15 14 12 5 17 3 9

样例输出

120

样例5

样例输入

8
2 2 7 2 2 7 2 2

样例输出

23

注意这里不保证样例强度

数据范围

$\texttt{Subtask1(10pts)}:n,m\leq 10$​。

$\texttt{Subtask2(10pts)}:n,m\leq 50$。

$\texttt{Subtask3(20pts)}:n,m\leq 300$。

$\texttt{Subtask4(10pts)}:$ $a_i$ 在 $(0,5000]$ 内随机。

$\texttt{Subtask5(10pts)}:$ $a_i$ 互不相同。

$\texttt{Subtask6(40pts)}:$ 无特殊限制。

对于 $100\%$ 的数据，$n\leq 3000,1\leq a_i\leq 10^9$。