- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
"کیا" عاشق "لیلی" شده و میخواهد برای "لیلی" یک دسته گل ببرد! برای این کار تصمیم گرفت از باغچهی کنار خیابان که \(n\) گل در یک ردیف دارد یک دسته گل بچیند. یک دسته گل شامل یک زیر مجموعه از گلهای باغچه است. او میداند "لیلی" وقتی یک دسته گل را میپسندد که شرایط زیر را داشته باشد.
- ارتفاع گلهایی که میچیند باید برابر باشد.
- ارتفاع همهی گلهایی که بین گلهای انتخاب شده قرار دارد باید بیشتر یا مساوی ارتفاع گلهای انتخاب شده باشد.
- باید همه ی گلهایی را که می چیند به "لیلی" بدهد. (یعنی حق استفاده نکردن از گل چیده شده ای را ندارد.)
حال کیا میخواهد بیشترین تعداد گل را برای "لیلی" ببرد طوری که شرایط بالا را داشته باشد. "کیا" عاشق شده و نمیتواند این مسئله را حل کند. به او بگویید که او حداکثر چند گل میتواند برای "لیلی" ببرد.
ورودی
در خط اول ورودی یک عدد صحیح \(n\) و در خط بعدی \(n\) عدد طبیعی داده میشود که عدد \(i\) ام برابر ارتفاع گل \(i\)ام است.
\[1 \leq n \leq 100\ 000\]\[1 \leq h_{i} \leq 1\ 000\ 000\ 000\]
خروجی
در یک خط خروجی بیشینه تعداد گلی که "کیا" میتواند برای "لیلی" ببرد را چاپ کنید.
مثال
ورودی نمونه ۱
5
8 9 8 3 8
خروجی نمونه ۱
2
توضیح نمونه ۱
کیا میتواند اولین و سومین گل را بچیند. او نمیتواند اولین، سومین و آخرین گل را بچیند؛ زیرا گلی با ارتفاع ۳ بین آخرین و سومین گل وجود دارد و از آنها کوتاهتر است.
ورودی نمونه ۲
2
8 2
خروجی نمونه ۲
1