حذف ارقام


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

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

ورودی🔗

سطر اول ورودی شامل عدد طبیعی nn، تعداد اعداد دنباله، است.

در سطر بعد nn عدد طبیعی aia_i آمده‌است که اعداد دنباله را نشان می‌دهند.

  • 1n500001\leq n \leq 50000

  • 1ai10181\leq a_i \leq 10^18

  • هیچ کدام از اعداد دنباله رقم 00 ندارند.

خروجی🔗

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

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

مثال🔗

ورودی نمونه ۱

4
63 54 45 36
Plain text

خروجی نمونه ۱

3
3 4 4 36
Plain text

ورودی نمونه ۲

6
8 16 16 1393 6 19 
Plain text

خروجی نمونه ۲

6
0 1 1 1 6 19
Plain text

۲۴امین دوره‌ المپیاد کامپیوتر - آزمون هفتم - ۱۳۹۳/۰۶/۱۹