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

---

روزبه دنباله‌ای مثل $a_1, a_2, a_3, ..., a_n$ انتخاب کرد و به ازای هر $i$ طول بلندترین زیردنباله‌ی صعودی که به عضو $i$ ام ختم می‌شود را محاسبه کرد و دنباله‌ی $d_1, d_2, d_3, ..., d_n$ را ساخت که $d_i$ بلندترین زیردنباله‌ی صعودی مختوم به $i$ است.

روزبه دنباله‌ی $d_1, d_2, ..., d_n$ را به محمدمهدی می‌دهد و از او میپرسد به ازای تمام دنباله‌های ممکن که دنباله‌ی ساخته شده از آن دنباله‌ی $d_1, d_2, ..., d_n$ شود، کمترین طول برای بزرگترین زیردنباله‌ی نزولی آن‌ها چقدر است؟

به محمد مهدی کمک کنید تا پاسخ این پرسش را بدهد.

ورودی

خط اول ورودی عدد $n$ که طول دنباله‌است آمده‌است. $(1 \leq n \leq 5\times10^5)$

در خط دوم $n$ عدد که با فاصله از هم جدا شده‌اند آمده‌است که عدد $i$ام مقدار $d_i$ است.

خروجی

در خط اول خروجی یک عدد که کمینه طول برای بزرگترین زیردنباله‌ی نزولی برای همه‌ی دنباله‌های ممکن برای انتخاب روزبه است.

خط دوم، دنباله‌ای مثال بزنید که طول بلندترین زیردنباله‌ی نزولی آن عدد کمینه باشد.

اعضای دنباله‌ی خروجی باید عدد طبیعی بوده و از یک‌میلیون بیشتر نباشند.

مثال

ورودی نمونه ۱

5
1 2 3 4 5

خروجی نمونه ۱

1
1 2 3 4 5 

---

ورودی نمونه ۲

13
1 2 2 3 3 3 3 3 4 5 5 6 7

خروجی نمونه ۲

5
19 74 66 1001 1000 444 323 98 5000 6000 5555 8500 9500

توضیحات

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

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

دنباله‌ای مثل $a_1, a_2, ..., a_n$ صعودی‌است اگر و تنها اگر به ازای هر $i$ که $1 \leq i < n$، $a_i \leq a_{i+1}$.

دنباله‌ای مثل $a_1, a_2, ..., a_n$ نزولی‌است اگر و تنها اگر به ازای هر $i$ که $1 \leq i < n$، $a_i \geq a_{i+1}$.