سوال ۲

خانم دکتر دنباله‌ای از اعداد طبیعی دارد. همان‌طور که می‌دانید دکتر‌ها برعکس مهندس‌ها از صعودی‌بودن دنباله‌ها لذت می‌برند ولی بلد نیستند دنباله‌هایشان را صعودی کنند. برای همین خانم دکتر از آقای مهندس خواسته‌است تا دنباله‌اش را برایش صعودی کند. (منظور از دنباله‌‌ی صعودی دنباله‌ای است که هیچ عضوی از آن از عضو قبلی‌اش کمتر نیست) آقای مهندس در هر حرکت می‌تواند یکی از ارقام یکی از اعداد دنباله را حذف کند. دقت کنید که وقتی تمامی ارقام یکی از اعداد دنباله را حذف کنیم مقدارش صفر خواهد شد.

او به عنوان یک مهندس مجبور است در کم‌ترین تعداد حرکت دنباله‌ را صعودی کند. این کم‌ترین تعداد حرکت چقدر است؟ هم‌چنین او می‌خواهد جمع اعداد دنباله‌ی نهایی که با کمترین تعداد حرکات به آن می‌رسد کمینه باشد. (در عین استفاده از کمترین تعداد حرکت) این مجموع کمینه را نیز پیدا کنید.

• سطر اول ورودی شامل عدد طبیعی $n$، تعداد اعداد دنباله، است.
• در سطر بعد $n$ عدد طبیعی $a_i$ آمده‌است که اعداد دنباله را نشان می‌دهند.
• $1 \leq n \leq 50000$
• $1 \leq a_i \leq 10^{18}$
• هیچ کدام از اعداد دنباله رقم $0$ ندارند.

در سطر اول خروجی کمترین تعداد حرکت برای صعودی کردن دنباله را چاپ کنید.

در سطر دوم $n$ عدد چاپ کنید که اعداد دنباله نهایی را نشان می‌دهند که هم باید صعودی باشند و هم مجموع‌شان کمینه شود. در صورت وجود چندین جواب هر کدام از آن‌ها را می‌توانید چاپ کنید.

نمره‌دهی این سوال به این شکل است که اگر کمترین تعداد حرکت برای صعودی کردن دنباله را اشتباه چاپ کنید نمره‌ای به شما تعلق نمی‌گیرد، در صورتی که کمترین تعداد حرکت درست باشد ولی مجموع اعداد دنباله‌ی نهایی کمینه نباشد، سه‌دهم نمره به شما تعلق می‌گیرد و تنها در صورتی نمره‌ی کامل می‌گیرید که هم کمترین تعداد حرکت درست باشد و هم مجموع اعداد دنباله‌ی نهایی کمینه باشد. (به ازای هر زیرمساله)

• زیرمسئله اول (۱۰ نمره): $n \leq 100$ و $a_i \leq 1000$
• زیرمسئله دوم (۲۰ نمره): $n \leq 100$ و $a_i \leq 10^6$
• زیرمسئله سوم (۳۰ نمره): $n \leq 500$ و $a_i \leq 10^{18}$
• زیرمسئله چهارم (۴۰ نمره): بدون محدودیت اضافی

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

• سوال بعد
• سوال قبل