【问题描述】 小 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。