2714 - 扑克(poker)

【问题描述】 小 W 手上有 N 堆扑克牌,为便于说明,给其编号为 1..N,第i(1≤i≤N)堆有ai 张扑克牌。 这天小W玩起了一个扑克牌的游戏,每次指定一个i和 j(1≤i≤j≤N),表示从第 i 堆一直到第j 堆,每堆移走一张扑克牌,前提是每堆至少有一张牌。

现在的问题是:用这样的方法将所有的扑克牌都移走,最少需要操作多少次?

比如有 5 堆牌,初始张数是:2 4 1 2 3 第 1 次 5..5:2 4 1 2 2 第 2 次 2..2:2 3 1 2 2 第 3 次 1..5:1 2 0 1 1 第 4 次 1..2:0 1 0 1 1 第 5 次 4..5:0 1 0 0 0 第 6 次 2..2:0 0 0 0 0

输入

第一行,一个单独的整数N。 接下来有 N 行,每行一个非负整数 ai,表示第 i 堆牌的数。

输出

一个单独的整数,表示移走所有的牌需要的最少操作次数。

样例

输入

5
2
4
1
2
3

输出

6

提示

【数据范围】 25%的数据,N≤20。 55%的数据,N≤1500。 100%的数据,1 ≤ N ≤ 100000,0 ≤ ai ≤ 100000。

题目参数

时间限制 1 秒
内存限制 32 MB
提交次数 0
通过人数 0
统计

上一题 下一题