* محدودیت زمان:‌ ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ------------------------------ بابای حسنی به حسنی سوالی را داده و به او گفته تا این سوال را حل کند. اما چون حسنی زیاد علاقه‌ای به حل سوال ندارد، از شما خواسته تا این سوال را برای او حل کنید. آرایه‌ای به نام $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 ```

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