Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0194 - OPENING CEREMONY

For the grand opening of the algorithmic games in NlogNsglow, a row of tower blocks is set to be demol- ished in a grand demonstration of renewal. Originally the plan was to accomplish this with controlled explo- sions, 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 / Incan- descent 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.

Task

        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 n 100 000. The second line contains n consecutive block heights hi for i = 1, 2, . . . , n, where 1 hi 1 000 000.

Output

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

stdin

stdout

1

6
2 1 8 8 2 3

5

2

5
1 1 1 1 10

2


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Nordic (NCPC) 2014.E

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.