- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
بله! زمان به سرعت می‌گذرد و لیته و فیته که به سختی به هم پیوند خورده‌اند قصد دارند به یاد خاطراتی که با هم روی سنِ سالن دارند، این بار در افتتاحیه کدکاپ برای شما نیز خاطره سازی کنند.
آن‌ها می‌خواهند این‌کار را با اجرای نمایشی فوق‌العاده روی سن انجام دهند.
روی سنِ سالن افتتاحیه دنباله‌ای از اعداد طبیعی نوشته شده است و لیته و فیته در دو طرف آن ایستاده‌اند. در مرحله $i$-ام یکی از این دو نفر به انتخاب خودشان یکی از اعضای دنباله که بین این دو نفر است و مقدارش برابر با عدد $i$ است را انتخاب می‌کند، خرامان به سمت آن عضو از دنباله می‌رود و روی آن می‌ایستد.
اگر در مرحله‌ی$k$-ام بین لیته و فیته هیچ عضوی با مقدار $k$ وجود نداشته باشد، نمایش به پایان می‌رسد.
فیته متوجه شد این که نمایش تا چند مرحله ادامه داشته باشد به حرکت‌های آن‌ها بستگی دارد. لیته می‌خواهد طوری حرکت‌ها انتخاب کنند تا نمایش بیشترین مقدار ممکن طول بکشد؛ شما به او بگویید که این نمایش حداکثر چندگام طول خواهد کشید.
ورودی
سطر اول ورودی شامل عدد طبیعی $n$ است که نشان‌دهنده طول دنباله اعداد روی سن است.
در سطر بعد $n$ عدد $a_i$ با فاصله از هم آمده‌اند. $$1 \le n \le 100\ 000$$ $$1 \le a_i \le n\ (1 \le i \le n)$$
خروجی
خروجی برنامه شامل تنها یک عدد است که نشان‌دهنده بیشترین طول نمایش خاطره‌ساز لیته و فیته است. در صورتی که آن‌ها نمی‌توانند حرکت کنند $-1$ چاپ کنید.
مثال
ورودی نمونه ۱
5
1 2 4 5 3
خروجی نمونه ۱
5
نمونه‌ی بالا دقیقا مانند عکس صورت سوال است. در این تست به ترتیب لیته، لیته، فیته، لیته، و فیته حرکت می‌کنند و از روی همه‌ی ۵ جایگاه سن گذر می‌کنند.
ورودی نمونه ۲
6
1 4 2 3 5 2
خروجی نمونه ۲
4
ارسال پاسخ برای این سؤال