• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون نهایی اول دوره ۲۷ المپیاد کامپیوتر

بهراد $n$ مین در یک ردیف پیدا کرده است که مین $i$ام در مختصات $x_i$ محور اعداد قرار دارد. او که می‌خواهد محیط را مین‌زدایی کند، تصمیم گرفته همه مین‌ها را منفجر کند.

برای انفجار هر مین باید نیرویی به آن وارد شود. اگر به یک مین به اندازه $k$ $(k \ge 1)$ نیرو وارد شود،‌ مین منفجر شده و به تمام مین‌هایی که در فاصله کمتر مساوی $k$ از آن مین قرار دارند نیز به اندازه $k$ نیرو وارد می‌کند (که باعث انفجار آن‌ها نیز می‌شود).

هر بار بهراد می‌تواند نیرویی به یک مین وارد کند و کل نیرویی که مصرف می‌کند برابر است با جمع همه نیرو‌هایی که مستقیما به مین‌ها وارد کرده است.

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

ورودی

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

در خط دوم $n$ عدد آمده است که عدد $i$ام، $x_i$، مکان مین $i$ام را که عددی صحیح است نشان می‌دهد.

$$1 \le n \le 300\ 000$$ $$0 \le x_i \le 10^{18}$$

دنباله $x$ اکیدا صعودی است.

خروجی

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

زیرمسئله‌ها

مثال

ورودی نمونه ۱

4
1 3 10 12

خروجی نمونه ۱

4

ورودی نمونه ۲

8
0 1 4 5 8 9 12 13

خروجی نمونه ۲

3