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

توی دوره نیمبو به تفریح کارآموزها اهمیت زیادی داده می‌شه و واسه همین تو زمان استراحت به کارآموزا می‌گن که بازی تتریس نیمبویی رو بازی کنن تا هم یه تفریحی واسشون باشه هم زمان استراحت یه جوری بگذره.

در بازی تتریس نیمبویی $n$ ستون وجود دارند که از چپ به راست با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند و ستون $i$ ام از $a_{i}$ مربع واحد تشکیل شده‌است.

هر بازیکن در هر حرکت می‌تواند یک بازه از ستون‌ها را انتخاب کند و به هرکدام یک مربع اضافه کند. (در واقع بازیکن اعداد $l$ و $r$ را انتخاب میکند و سپس به ازای هر $l \le j \le r$ ، مقدار $a_{j}$ را یکی زیاد می‌کند.)

هدف بازی یکسان کردن طول تمام ستون ها در کم‌ترین تعداد مرحله است.

حالا مهرداد که از این بازی خوشش نیومده ازتون می‌خواد تا بهش بگین که این کم‌ترین تعداد مرحله چندتاست تا بتونه سریع بازی رو تموم کنه و به بقیه کاراش برسه.

ورودی

در خط اول ورودی عدد $n$ ، تعداد ستون‌ها می‌آید.

در خط بعدی $n$ عدد آمده که عدد $i$ ام آن $a_{i}$ است که تعداد مربع‌های ستون $i$ ام را نشان می‌دهد.

$$1 \le n \le 1\ 000\ 000$$ $$1 \le a_{i} \le 1\ 000\ 000\ 000$$

خروجی

در خروجی یک عدد که کم‌ترین تعداد مراحل برای رسیدن به هدف بازی است را چاپ کنید.

مثال

ورودی نمونه ۱

3
1 3 2

خروجی نمونه ۱

3

دوبار مقدار ستون اول (بازه $[1,1]$ ) را، و یکبار مقدار ستون سوم (بازه $[3,3]$ ) را زیاد میکنیم.

ورودی نمونه ۲

5
4 3 1 3 7

خروجی نمونه ۲

6

سه بار بازه $[1,4]$ را انتخاب میکنیم. سپس یکبار بازه $[2,4]$ و دو بار بازه $[3,3]$ را انتخاب میکنیم.