Get Maximum

Choose a non-empty contiguous range and take a positive integer number of items from each pile, no more than that pile's capacity, so that the amounts taken strictly increase from left to right. Find the maximum number of items that can be taken. A prefix that takes 0 contributes nothing to the total and can simply be dropped, so it does not affect the optimal answer.

输入格式

The first line contains n; the second line contains the pile capacities. 1≤n≤5000, 1≤capacity≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

6
7 4 5 2 6 5

输出：

12

样例 2

输入：

6
2 9 4 7 5 2

输出：

16

样例 3

输入：

4
2 5 6 7

输出：

20

样例说明

The answers are 12, 16 and 20.