• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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 xx-th floors in all the blocks simultaneously, for user’s choice of the floor number xx. In the latter case, the blocks that are less than xx floors high are left untouched, while for blocks having more than xx floors, all the floors above the removed xx-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.

ورودی

The first line of input contains the number of blocks nn, where 2n1000002 \le n \le 100 000. The second line contains nn consecutive block heights hih_i for i=1,2,...,ni = 1, 2, ..., n, where 1hi10000001 \le h_i \le 1 000 000.

خروجی

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

مثال

ورودی نمونه ۱

6
2 1 8 8 2 3
Plain text

خروجی نمونه ۱

5
Plain text

ورودی نمونه ۲

5
1 1 1 1 10
Plain text

خروجی نمونه ۲

2
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.