زیبایی بیش از همه
Problem
در پارک شهر پیتسبورگ یک کوچه فوق العاده وجود دارد که از N درخت در یک ردیف کاشته شده اند، هر کدام از یکی از گونه های K. با میزبانی پیتزبورگ مسابقات قهرمانی برنامه نویسی باز Byteland، تصمیم گرفته شد که عرصه بزرگی برای میزبانی این مسابقات ساخته شود. پس طبق این طرح قرار بود کل کوچه قطع شود. اما وزارت درختان و بوته ها با این تصمیم مخالفت کرده و خواستار تنها ماندن برخی از درختان شد. طبق طرح ساخت و ساز جدید، تمام درختانی که قطع نمی شوند باید یک قطعه پیوسته تشکیل دهند که زیربخش اصلی است. هر یک از گونه های درخت K باید حداقل یک نسخه حفظ شود. وظیفه شما یافتن قسمتی از کوچکترین طول است که محدودیت های مشخص شده را برآورده می کند.
ورودی
خط اول فایل ورودی شامل دو عدد N و K است ( 1 ≤ N , K ≤ 250000). خط دوم فایل ورودی حاوی N عدد است (با فاصله از هم جدا شده اند)، عدد i-امین خط دوم رنگ درخت i-امین را از سمت چپ در کوچه مشخص می کند. تضمین شده است که حداقل یک درخت از هر رنگ وجود دارد
خروجی
در فایل خروجی دو عدد، مختصات انتهای چپ و راست قطعه با حداقل طولی که شرط را برآورده می کند چاپ کنید. اگر چندین پاسخ بهینه وجود دارد، یکی را چاپ کنید.
<بدن>
| ورودی |
خروجی |
|
5 3
1 2 1 3 2
|
2 4 |
|
6 4
2 4 2 3 3 1
|
2 6 |