书架上有按编号 1～N 依次排列的 N 类卡片，第 i 类卡片有 A_i 张。每次操作时，你可以选择一段编号连续的区间 [l, r]，并从其中的每一类里各抽走一张卡片；但要求该区间内的每一类卡片在本次操作前都至少还有一张。

请你求出把所有卡片全部抽光所需的最少操作次数。

• 第一行一个整数 N。

• 接下来 N 行，每行一个整数 A_i，表示第 i 类卡片的张数。

一行一个整数，表示抽光所有卡片的最少操作次数。

本题使用标准输入输出（stdin/stdout），不需要写 freopen。

样例解释 1

开始时各类卡片数量为 2, 4, 1, 2, 3。一种最优的操作序列为：

• 抽走区间 [1,2]，得到 1,3,1,2,3；

• 抽走区间 [2,2]，得到 1,2,1,2,3；

• 抽走区间 [2,5]，得到 1,1,0,1,2；

• 抽走区间 [1,2]，得到 0,0,0,1,2；

• 抽走区间 [4,5]，得到 0,0,0,0,1；

• 抽走区间 [5,5]，得到 0,0,0,0,0。

共 6 次操作。

数据范围与约定

• 对于约 40% 的数据，1 ≤ N ≤ 2000；

• 对于约 20% 的数据，1 ≤ N ≤ 20000；

• 对于 100% 的数据，1 ≤ N ≤ 100000。

• 所有 A_i 满足 0 ≤ A_i ≤ 100000。