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

هر روز صبح با طلوع خورشید هر عنکبوتی که ببیند ارتفاعش هم از عنکبوت سمت راست (در صورت وجود) و هم از عنکبوت سمت چپ خود (در صورت وجود) پایین‌تر است از حسودی امید به زندگی خود را از دست داده و با پاره کردن تارش، خودکشی می‌کند. منظور از ‎«عنکبوتِ سمت راست»، نزدیک‌ترین عنکبوت زنده در سمت راست است؛ هم‌چنین برای سمت چپ.

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

• در خط اول N‎ ، تعداد عنکبوت‌ها داده‌شده است.
• در خط بعد، ‎N‎ عدد ‎$d_1$‎ و … و ‎$d_N$‎ با یک فاصله از هم داده شده‌اند که فاصله‌ی عنکبوت‌ها از سقف را نشان می‌دهند.
• می‌دانیم همواره عنکبوت‌های اول و آخر به سقف چسبیده‌اند.
• $3 \le N \le 10^6$‎.
• $0 \le d_i \le 10^9$‎.
• $D_i$‎ها صحیح و دوبه‌دو متفاوت هستند.

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

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

• سوال بعد
• سوال قبل