• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۱۰۲۴ مگابایت

---

عمو دنباله ی اعداد \(A = a_1, a_2, \dots, a_N\) را از دفترچه خاطرات بچگی‌اش پیدا کرده است. در کنار این دنباله نوشته شده بود که طول بلندترین زیردنباله صعودی آن را بیابید. عمو که دیگر پیر شده بود، برای اینکه خودش را به چالش بکشد سوال را به شکل زیر عوض کرد و سعی کرد آن را حل کند. به جای بلندترین زیردنباله صعودی، بلندترین دنباله مانند \(B = b_1, b_2, \dots, b_M\) را پیدا کنید که زیر دنباله دابل صعودی باشد. یعنی دو شرط زیر را داشته باشد:

• دنباله‌ی \(B\) یک زیردنباله از \(A\) باشد.
• برای تمامی \(i\) ها که \(1 \leq i \leq M - 2\)، شرط \(b_i < b_{i+2}\) برقرار باشد.

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

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

ورودی

• اولین خط ورودی شامل یک عدد صحیح \(N\) است که تعداد عناصر دنباله \(A\) را نشان می‌دهد.
• خط دوم شامل \(N\) عدد صحیح است که مقادیر \(a_1, a_2, \dots, a_N\) را نشان می‌دهد. هر عدد \(a_i\) مقداری بین \(1\) و \(N\) دارد.

خروجی

یک عدد صحیح که طولانی‌ترین دنباله \(B\) که شرایط فوق را برآورده می‌کند، نشان می‌دهد.

محدودیت‌ها

\[1 \le N \le 5000\] \[1 \le A_i \le N\]

مثال

ورودی نمونه ۱

8
1 5 7 8 6 3 4 2

خروجی نمونه ۱

4

ورودی نمونه ۲

8
1 4 2 8 5 7 1 4

خروجی نمونه ۲

5

ورودی نمونه ۳

2
1 2

خروجی نمونه ۳

2

ورودی نمونه ۴

6
2 2 3 3 5 5

خروجی نمونه ۴

6