* محدودیت زمان:‌ ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ------------------------------ بابای حسنی به حسنی سوالی را داده و به او گفته تا این سوال را حل کند. اما چون حسنی زیاد علاقه‌ای به حل سوال ندارد، از شما خواسته تا این سوال را برای او حل کنید. آرایه‌ای به نام $a$ به طول $ n $ داریم. می‌خواهیم بلندترین زیردنباله‌ای از آرایه را پیدا کنیم که *صعودی-نزولی* باشد. حسنی به دنباله $b_0, b_1, ... , b_{k-1\ }$ *صعودی-نزولی* می‌گوید اگر سه شرط زیر برای آن برقرار باشد: + به ازای برای هر $i$ فرد که $ 0 \lt i \lt k-1 $ داشته باشیم : $ b_{i-1} \lt b_{i} \gt b_{i+1} \ $ + به ازای برای هر $i$ زوج که $ 0 \lt i \lt k-1 $ داشته باشیم : $ b_{i-1} \gt b_{i} \lt b_{i+1} \ $ + برای $i$ برابر با صفر هم داشته باشیم: $b_0 \lt b_1$ حال شما باید طول بلندترین زیردنباله‌ای از آرایه $a$ که *صعودی-نزولی* است را پیدا کنید و آن را چاپ کنید. **نکته:** به آرایه $b$ یک زیردنباله از آرایه $a$ می‌گوییم اگر بتوان با حذف تعدادی عضو از آرایه $a$ به آرایه $b$ رسید. # ورودی در اولین خط ورودی عدد $n$ و در خط بعدی $n$ عدد امده است که عدد $i$ ام مقدار خانه $i$ ام آرایه است. $$ 1 \le n \le 100\ 000$$ $$ |a_i| \le 10^9$$ # خروجی در تنها خط خروجی طول بلندترین زیردنباله *صعودی-نزولی* را بگویید. # مثال # ورودی نمونه ۱ ``` 7 5 1 9 2 3 6 2 ``` # خروجی نمونه ۱ ``` 5 ``` برای مثال دنباله $<1, 9, 2, 3, 2>$ یکی از جواب‌های ممکن است. # ورودی نمونه ۲ ``` 4 1 2 1 2 ``` # خروجی نمونه ۲ ``` 4 ``` در این حالت کل آرایه $a$ *صعودی-نزولی* است. # وروی نمونه ۳ ``` 4 2 1 2 1 ``` # خروجی نمونه ۳ ``` 3 ``` ------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> اگر دو عنصر متوالی و مساوی وجود داشت، می‌توانیم یکی را به دلخواه حذف کنیم چون در جواب مسئله تاثیری ندارد. اگر سه عنصر متوالی وجود داشته باشد که صعودی باشند یعنی اولی کمتر از دومی و دومی کمتر از سومی باشد می‌توانیم عنصر دوم را حذف کنیم. (چرا؟) </details> <details class="blue"> <summary> اثبات راهنمایی ۱ </summary> اگر دنبال بهینه‌ای وجود داشته باشد که عنصر وسط (یعنی دوم) در این دنباله باشد طبق تعریف دنباله صعودی-نزولی، ممکن نیست هر سه عنصر در این دنباله باشند. پس می‌توان جای عنصر دوم یکی از دو عنصر که استفاده نشده را قرار داد. (در صورتی که این عنصر، اندیس فرد داشت جای آن عنصر بعدی که بزرگ‌تر است (و در نتیجه بهتر است) را قرار می‌دهیم و در غیر این صورت عنصر دیگر) </details> <details class="blue"> <summary> راهنمایی ۲ </summary> اگر *k* عنصر متوالی صعودی وجود داشت طبق راهنمایی قبل فقط اولی و اخری را نگه می‌داریم و بقیه را حذف می‌کنیم. همینطوری اگر *k* عنصر متوالی نزولی وجود داشت اولی و اخری را نگه می‌داریم و بقیه را حذف می‌کنیم. </details> <details class="blue"> <summary> راه حل </summary> بعد از حذف عنصر‌های اضافه که در راهنمایی ۲ گفته شد، می‌توانید مشاهده کنید که دنباله باقی‌مانده، یک دنباله صعودی-نزولی است. البته ممکن است نیاز باشد اولین عنصر را نیز حذف کنید در صورتی که عنصر اولی بزرگتر از عنصر بعدی باشد. دنباله جدید صعودی - نزولی است چون عضو دوم بزرگتر از عضو اول است و اگر عنصر سوم بزرگتر از دومی باشد سه عنصر متوالی صعودی پیدا شده که تناقض دارد. پس عنصر سوم کوچک‌تر از عنصر دومی است. حالا اگر عنصر چهارم کوچک‌تر از عنصر سوم باشد دوباره سه عنصر متوالی نزولی پیدا شده که تناقض دارد پس عنصر چهارم بزرگ‌تر از عنصر سوم است. اگر همین روال را ادامه بدهیم می‌بینیم که دنباله صعودی-نزولی است. از طرفی این دنباله بلندترین است چون دنبال بهینه‌ای وجود داشته باشد که عنصر وسط (یعنی دوم) در این دنباله باشد طبق تعریف دنباله صعودی-نزولی ممکن نیست هر سه عنصر در این دنباله باشند پس می‌توان جای عنصر دوم یکی از دو عنصر که استفاده نشده را قرار داد (در صورتی که این عنصر، اندیس فرد داشت جای آن عنصر بعدی که بزرگ‌تر است (و در نتیجه بهتر است) را قرار می‌دهیم و در غیر این صورت عنصر دیگر) </details>