• محدودیت زمان:‌ ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

بابای حسنی به حسنی سوالی را داده و به او گفته تا این سوال را حل کند. اما چون حسنی زیاد علاقه‌ای به حل سوال ندارد، از شما خواسته تا این سوال را برای او حل کنید.

آرایه‌ای به نام \(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