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

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

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