Leaking Dike

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

فرض کنید روستا مجموعه‌ای از ساختمان‌های دوبعدی روی محور $x$هاست. ساختمان‌ها به هم چسبیده‌اند و همه‌ی آن‌ها سقفی افقی با عرض یک متر دارند، هر چند ارتفاع سقف‌ها می‌تواند متفاوت باشد. سد، که در ابتدای روستا واقع شده، حداقل یک متر از دیگر ساختمان‌ها بلندتر است و از بالای آن با نرخ یک متر مربع بر دقیقه نشت می‌کند. همچنین یک دیوار در انتهای روستا به بلندی سد وجود دارد. برنامه‌ای بنویسید که برای یک روستایی خاص، زمان باقی مانده پیش از این که خانه‌اش یک متر زیر آب رود را محاسبه کند.

• ورودی از چند سناریو تشکیل شده است. هر سناریو با یک خط شامل عدد صحیح $n$ $(1 \leq n \leq 10,000)$ آغاز می‌شود که $n$ تعداد ساختمان‌هاست. فرض کنید که سد در مختصات صفر محور $x$هاست و از زمان صفر شروع به نشت می‌کند.
• خط بعد شامل $n$ عدد نامنفی است که با فاصله از هم قرار گرفته‌اند و از $10,000$ بیش‌تر نیستند. $i$امین عدد ارتفاع ساختمانی است که در بازه‌ی $[i-1,i]$ روی محور $x$ها واقع شده است.
• آخرین خط شامل شماره‌ی ساختمانی است که باید برای زمان باقی مانده پیش از آن که 1 متر زیر آب رود را محاسبه کنید. فرض کنید که ساختمان‌ها از چپ به راست شماره گذاری شده و سمت چپ‌ترین ساختمان با عدد $1$ شماره‌گذاری شده است.
• ورودی با خطی شامل $"0"$ خاتمه می‌یابد.

به ازای هر سناریو، در یک خط زمان باقی مانده (به دقیقه) تا زیر آب رفتن ساختمان داده شده به میزان $1$ متر را نمایش دهید.

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

• سوال بعد