在诸神之战后，仙宫的神王奥丁正式将自己的天父地位交给托尔，因此他在原有的超能力之外，额外得到了作为神王特有的奥丁之力（Odinforce），托尔肩负起了守护人间的使命。

邪恶的变种人来到地球并在地球上建造起了 N 个要塞，连接成一条直线，每个要塞由一个生命值为 a_i 的变种人首领守护。

托尔拿起自己的雷神之锤，准备给敌人致命的一击，为了提高击杀效率，托尔不会逐个要塞击杀。他用雷神之锤引发天雷之怒，每次击杀都会选择一段守卫的生命值均大于 0 的连续区间 [L,R]，将这段区间中的守卫者生命值同时减少 1。

当守卫生命值减少到 0，这个要塞即被攻破。某个要塞一旦被攻破，下次托尔选择击杀区间时，不会再包含这样的要塞，要知道天雷之怒的力量实在太强大了，如果滥用不仅会伤及无辜，也会额外的消耗托尔的神力。

请编程计算出，如果托尔按照该方法攻破所有的要塞，至少需要击杀的次数？

第一行输入一个整数 n，表示要塞的数量。

第二行包含 n 个整数，相邻两数间用一个空格隔开，第 i 个整数 a_i 代表要塞中守卫者的生命值。

输出一个整数，代表托尔需要的最少击杀次数。

【样例解释】

一种可行的击破要塞，选择击杀区间的最佳方案是，依次选择：

[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。

【数据规模与约定】

对于 30\% 的数据，1 ≤ n ≤ 10 ；

对于 70\% 的数据，1 ≤ n ≤ 1000 ；

对于 100\% 的数据，1 ≤ n ≤ 100000 , 0 ≤ a_i ≤ 10000 。

NOIP2018 提高组 D1T1

贪心