#6811. [SeqOI 21W] Qunseece

内存限制:128 MiB 时间限制:500 ms 输入文件:baloni.in 输出文件:baloni.out
题目类型:传统 评测方式:无测试数据
上传者: Ericnth


There are N balloons floating in the air in a large room, lined up from left to right. Young Perica likes to play with arrows and practice his hunting abilities. He shoots an arrow from the left to the right side of the room from an arbitrary height he chooses. The arrow moves from left to right, at a chosen height H until it finds a balloon. The moment when an arrow touches a balloon, the balloon pops and disappears and the arrow continues its way from left to right at a height decreased by 1. Therefore, if the arrow was moving at height H, after popping the balloon it travels on height H-1. Our hero’s goal is to pop all the balloons using as little arrows as possible.

在一个大房间的空气中从左到右漂浮着 N 个气球。Nth 喜欢通过射箭来练习他的射击能力。对于他射出的每支箭,他可以选择任意一个高度 H ,然后,这支箭在高度 H 从左向右移动,直到射中一个气球。当箭头触及气球时,气球爆裂消失,同时这支箭高度减小 1 ,在高度 H-1 继续从左向右继续移动。 Nth 的目标是用最少支箭射掉所有的气球。

来源:COCI 2015 Round 1


The first line of input contains the integer N (1 ≤ N ≤ 1 000 000). The second line of input contains an array of N integers H_i. Each integer H_i (1 ≤ H_i ≤ 1 000 000) is the height at which the i^{th} balloon floats, respectively from left to right.

第一行一个整数 n (1 \le n \le 1,000,000)。 第二行包含一个有 n 个整数的数组 H_i 每个 H_i 中的整数( 1 \le H_i \le 1,000,000 )从左到右分别是第 i 个气球漂浮的高度。


The first and only line of output must contain the minimal number of times Perica needs to shoot an arrow so that all balloons are popped.

输出仅一行一个整数,表示 Nth 射爆所有气球需要最少几支箭。


Input #1

2 1 5 4 3

Output #1


Input #2

1 2 3 4 5

Output #2


Input #3

4 5 2 1 4

Output #3




In test cases worth 40%, it will hold N ≤ 5,000.

对于 40\% 的数据,符合 N \leq 5,000

Clarification of the first example: Our hero shoots the arrow at height 5 - which destroys [5, 4, 3], and shoots an arrow at height 2 - which destroys [2, 1].

样例1解释: Nth第1支箭的初始高度5,顺序射掉高度为5,4,3的气球,Nth第2支箭的初始高度2,顺序射掉高度为2,1的气球。