建筑师

题目描述

太阳以西，梦无尽头。

因为Orange丰富的想象力，因此他被任命为秘境的"建筑师"，他需要在秘境中建造一座"建筑"，建筑是一个由若干"方块"构成的二维图形。

"建筑师"Orange拥有一根神秘的法杖，每次他用法杖敲击地面，地面上 $[l,r]$ 的区间就会浮现出一排"方块"。若原来的位置存在"方块"，那么原来的"方块"就会被新生成的"方块"给顶起来。

例如，原来地面为如下所示，其中#表示"方块"，_表示空地:

_ _ _ # # _ _
1 2 3 4 5 6 7

当Orange敲击法杖并让 $[2,6]$ 生成"方块"时，地面则会变成如下所示：

      # #
_ # # # # # _
1 2 3 4 5 6 7

由于每次敲击法杖都会消费Orange $1$ 点魔力值，因此Orange想请问你，如果给定"建筑"的图纸，他最小要消耗多少点魔力值，才能完成"建筑"。

特别的，在最开始时，地面上什么也没有。

输入格式

第一行为一个整数 $n$，表示"建筑"的长度。 为了输入更加方便，接下来输入 $n$ 个整数 $a_i$，其中 $a_i$ 表示在第 $i$ 个位置应该有多少个方块。

为了尊重牛顿，输入保证在一个位置上不会存在方块悬空的情况，即如下情况:

  #

_ # _

数据范围

$1\le n, a_i \le 10^5$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

6
4 3 2 5 3 5

样例输出 #1

9

提示

样例所示的"建筑"如下所示：

      #   #
#     #   #
# #   # # #
# # # # # #
# # # # # #
1 2 3 4 5 6

可以通过如下过程构造：

1. 选择区间 $[1,6]$

# # # # # #
1 2 3 4 5 6

2. 选择区间 $[1,6]$

# # # # # #
# # # # # #
1 2 3 4 5 6

3. 选择区间 $[1,2]$

# #
# # # # # #
# # # # # #
1 2 3 4 5 6

4. 选择区间 $[1,1]$

# 
# #
# # # # # #
# # # # # #
1 2 3 4 5 6

5. 选择区间 $[4,6]$

# 
# #   # # #
# # # # # #
# # # # # #
1 2 3 4 5 6

6. 选择两次区间 $[4,4]$

      #
#     #
# #   # # #
# # # # # #
# # # # # #
1 2 3 4 5 6

7. 选择两次区间 $[6,6]$

      #   #
#     #   #
# #   # # #
# # # # # #
# # # # # #
1 2 3 4 5 6

可以证明这是一种最优的构造方案。