+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک روز گرم تابستانی بچه‌ها تو ساحل مشغول ساخت برج های شنی هستند. تا پایان روز آن‌ها موفق به ساخت $n$ برج شنی در یک ردیف می‌شوند. آن‌ها برج‌ها را از چپ به راست با شماره های ١ تا $n$ شماره گذاری می‌کنند. ارتفاع برج $i$ام برابر $h_i$ است. در هنگام رفتن از ساحل نابغه متوجه می‌شود که برج‌ها به ترتیب ارتفاع نیستند و ظاهری زشت دارند. آن ها تصمیم می‌گیرند که ترتیب برج‌ها را به صورتی دربیاورند که برای هر $i$ بین $1$ تا $n - 1$ داشته باشیم $h_i \leq h_{i+1}$. نابغه الگوریتم زیر را برای مرتب‌سازی پیشنهاد می‌کند: + برج‌ها به بلوک‌هایی افراز شوند که هر بلوک شامل تعدادی برج متوالی باشد. هر بلوک حداقل شامل یک برج باشد. لزومی ندارد بلوک‌ها اندازه‌ی یکسانی داشته باشند. طبیعتاً هر برج متعلق به دقیقاً یک بلوک خواهد بود. + هر بلوک به صورت مستقل به صورت غیرنزولی مرتب سازی شود. بدیهی است اگر تنها یک بلوک در نظر بگیریم که شامل همه‌ی برج‌ها باشد، با الگوریتم بالا همه‌ی برج‌ها بصورت غیرنزولی مرتب می‌شوند. اما از آنجا که بچه‌ها می‌خواهد جلوی نابغه خودی نشان دهند، تصمیم گرفته‌اند با بیشترین تعداد بلوک این کار را انجام دهند. به بچه ها کمک کنید که تعداد ماکزیمم بلوک‌ها را محاسبه کنند. # ورودی در خط اول $n$ (تعداد برج‌ها) آمده است. در خط بعدی $n$ عدد که نشان دهنده ارتفاع برج‌ها ($h_i$ها) از چپ به راست هستند آمده است. $$1 \leq n \leq 10^6$$ $$1 \leq h_i \leq 10^9$$ # خروجی در تنها خط خروجی شما باید ماکزیمم تعداد بلوک‌ها را که منجر به مرتب‌سازی برج‌ها می‌شود را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 2 3 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 4 2 1 3 2 ``` ## خروجی نمونه ۲ ``` 2 ```

حل سؤال در بانک سؤالات