---------- 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 \le n \le 100 000$. The second line contains $n$ consecutive block heights $h_i$ for $i = 1, 2, ..., n$, where $1 \le h_i \le 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 ``` 6 2 1 8 8 2 3 ``` ## Sample Output 1 ``` 5 ``` ## Sample Input 2 ``` 5 1 1 1 1 10 ``` ## Sample Output 2 ``` 2 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> فرض کنید ما فقط می‌توانیم تعدادی طبقه حذف کنیم. در این صورت با کمی بررسی در می‌یابیم که حداقل تعداد حرکت لازم برای از بین بردن کل بلوک‌ها، برابر با ارتفاع بلند‌ترین برج ماست. </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> حال به حل مسئله می‌پردازیم. بدون لطمه خوردن به کلیت مسئله فرض کنید اول تمام ستون‌ها و سپس تمام طبقات موردنظر را حذف می‌کنید. در این صورت پس از حذف ستون‌ها، طبق راهنمایی یک تعداد حرکات شما برابر با ارتفاع بلندترین برج است. بنابراین بهینه‌ترین حالت ممکن این است که اگر می‌خواهیم دقیقا $k$ ستون حذف کنیم،‌ آن $k$ ستونی را حذف کنیم که بیشترین ارتفاع را دارند. در این حالت تعداد حرکات ما برابر است با $k$ + ارتفاع $k + 1$ امین بلندترین برج. ($k$ حرکت برای حذف کردن $k$ تا بلندترین برج و ارتفاع $k+1$ امین برج برای حذف گردن بقیه) به دست آوردن مقادیر بالا به ازای هر $k$، پس از مرتب‌سازی برج‌ها بر اساس ارتفاعشان به سادگی امکان‌پذیر است. </details>