题目描述

小婷有编号 $1$ 到 $N$ 的卡牌，第 $i$ 种有 $a_i$ 张。一次可以选择 $l\le r$，并各打出一张编号为 $l,l+1,\ldots,r$ 的牌。求清空所有卡牌最少需要多少次。

输入格式

第一行整数 $N$，接下来 $N$ 行依次给出 $a_i$。

输出格式

输出最少次数。

输入

14
61570
88027
21076
8548
36238
34619
82536
61038
33774
77356
96257
50586
5826
21119

输出

241410

输入

32
88468
89816
12378
42674
92497
87628
55891
3580
58060
85007
26682
67155
16683
5342
6845
62575
79173
88150
70395
59848
41452
70886
19727
37016
23591
64065
24913
63442
224
79126
91497
69555

输出

591642

输入

39
61762
15820
34800
51761
57816
20220
98028
46248
41612
46710
74440
37481
52798
52253
61910
2575
69217
1272
57895
84021
78022
58288
94460
47184
351
93680
37866
84609
95323
35454
23811
3432
23556
545
64967
48670
65839
63601
29517

输出

677432

数据范围

$1\le N\le10^5$，$0\le a_i\le10^5$。