[email protected] #5 (Binary) Search

#### Start

2018-04-23 08:18 AKDT

## [email protected] #5 (Binary) Search

#### End

2018-04-30 08:18 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -954 days 0:22:03

168:00:00

0:00:00

# Problem AOpening Ceremony

From Wikipedia under Creative Commons licence, by G Laird

For the grand opening of the algorithmic games in NlogNsglow, a row of tower blocks is set to be demolished in a grand demonstration of renewal. Originally the plan was to accomplish this with controlled explosions, one for each tower block, but time constraints now require a hastier solution.

To help you remove the blocks more rapidly you have been given the use of a Universal Kinetic / Incandescent Energy Particle Cannon (UKIEPC). On a single charge, this cutting-edge contraption can remove either all of the floors in a single tower block, or all the $x$-th floors in all the blocks simultaneously, for userâ€™s choice of the floor number $x$. In the latter case, the blocks that are less than $x$ floors high are left untouched, while for blocks having more than $x$ floors, all the floors above the removed $x$-th one fall down by one level.

Given the number of floors of all towers, output the minimum number of charges needed to eliminate all floors of all blocks.

## Input

The first line of input contains the number of blocks $n$, where $2 \leq n \leq 100\, 000$. The second line contains $n$ consecutive block heights $h_ i$ for $i=1,2,\ldots ,n$, where $1 \leq h_ i \leq 1\, 000\, 000$.

## Output

Output one line containing one integer: the minimum number of charges needed to tear down all the blocks.

Sample Input 1 Sample Output 1
6
2 1 8 8 2 3

5

Sample Input 2 Sample Output 2
5
1 1 1 1 10

2