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

میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، تصمیم به ترک دنیای کدزنی گرفتند و خود را برای لیگ‌ جهانی چندمینو آماده می‌کنند.

چندمینو، همانند دومینو است با این تفاوت که چندمینوها ارتفاعشان لزوما یکسان نیست. یک چندمینو مانند $A$ به شرطی چندمینوی دیگر مانند $B$ را می‌اندازد که فاصله‌شان کمتر از ارتفاع $A$ باشد و به همین ترتیب چندمینو $B$ هم پس از انداخته‌شدن توسط $A$، چندمینوهای بعدی خودش را به شرط کمتر بودن فاصله‌‌شان از ارتفاع $B$ می‌اندازد.

دقت کنید که چندمینوها در یک ردیف چیده شده‌اند و تنها در یک جهت، می‌افتند. (یعنی یک چندمینو پس از افتادن یا چندمینوهای قبلی خودش را می‌اندازد یا چندمینوهای بعدی)

در لیگ چندمینو هر تیم در شروع تنها می‌تواند یک چندمینو را بیندازد. چنانچه پس از انداختن اولین چندمینو همه چندمینوها نیفتد، داوران در ازای دادن یک اخطار به آن تیم اجازه می‌دهند که یکبار دیگر چندمینویی دیگر را بیندازد و این روال تا زمانی که همه چندمینوها بیفتد ادامه دارد. یک تیم در یک مرحله می‌تواند هریک از چندمینوها را به هریک از ۲ جهت راست یا چپ که انتخاب کرد بیندازد.

در واقع تعداد اخطارهای یک تیم یکی کمتر از تعداد چندمینوهایی است که دستی انداخته است.

پارسا $n$ چندمینو‌ را در یک ردیف چیده است به طوری که فاصله دو چندمینوی متوالی دقیقا ۱ واحد است.

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

ورودی

در خط اول ابتدا $n$ که تعداد چندمینوهاست به شما داده می‌شود.

در خط بعدی $n$ عدد به شما داده می‌شود که عدد $i$-ام ارتفاع چندمینو $i$-ام است. (می‌دانیم که ارتفاع چندمینوها اعدادی طبیعی و حداکثر ۲۰۰۰۰۰ است.) $$1 \le n \le 200\ 000$$

خروجی

در یک خط کمترین اخطاری که تیم میلاد اینا دریافت می‌کند را چاپ کنید.

مثال

ورودی نمونه ۱

3
1 2 1

خروجی نمونه ۱

1

ورودی نمونه ۲

7
1 2 1 1 4 2 1

خروجی نمونه ۲

1