المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:عملی:سوال ۱۱

عنکبوت

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

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

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

‎ورودی

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

خروجی

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

محدودیت‌ها

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

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
5
‎0 5 3 10 0‎
‎2‎

ابزار صفحه