Maximum Number of Products You Can Pick

Choose a non-empty contiguous subarray and take at least one item, and at most its stock, from each chosen shelf, so that the amounts taken are strictly increasing from left to right. Find the maximum total number of items. You cannot skip shelves in the middle of the chosen subarray.

输入格式

The first line contains n and the second line contains products. 1≤n≤5000, 1≤products[i]≤10^9. This full range comes from the Constraints in the raw body, not from the cleaned-up version truncated by HTML.

输出格式

Output a single integer, the answer.

样例 1

输入：

6
2 9 4 7 5 3

输出：

16

样例 2

输入：

3
7 5 3

输出：

9

样例 3

输入：

3
1 1 1

输出：

1

样例说明

The answers are 16, 9 and 1 respectively. In the second example you can choose just the first two shelves and take 4 and 5 for 9; taking all three shelves gives only 1+2+3=6.