+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا بچه‌ای شلخته و نامنظم است که اتاقش شبیه شهر ارواح است**!** در یکی از روزهای مه‌آلود بهاری، مادر رادزینکا خواست تا اتاق او را جاروبرقی بکشید که ناگهان با انبوه لنگه جوراب‌های پخش و پلای او روبرو شد. مادر که به خشم آمده بود، شروع به جفت‌ کردن جوراب‌های هم‌رنگ کرد و تصمیم گرفت هر جورابی که اضافه آمد را دور بریزد و جوراب‌های جفت‌ شده‌ را در کمد قرار دهد، بلکه اتاق اندکی خلوت شود. از آن‌جایی که جوراب‌های رادزینکا ورزشی است، بر روی هر لنگه یک عدد نوشته شده است.جوراب‌ها به ترتیب با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند. مادر رادزینکا دوست دارد به نحوی جوراب‌ها را جفت کند که چهار شرط زیر (به همین ترتیب اولویت) رعایت شود: + دو لنگه‌ای که با هم جفت می‌شوند، رنگ یکسانی داشته باشند. + تعداد جوراب‌های جفت شده بیشینه شود تا کمترین تعداد جوراب دور ریخته شود. + اگر قرار است $k$ جفت انتخاب کند، آن‌ $k$ جفت را به گونه‌ای انتخاب کند که جمع اعداد موجود بر روی جوراب‌ها کمینه شود (مادر رادزینکا از اعداد بزرگ خوشش نمی‌آید). + در جفت کردن ایده‌آل مادر رادزینکا، با رعایت کامل سه شرط بالا، تلاش می‌شود شماره جوراب‌های جفت شده تا حد امکان به هم نزدیک‌تر باشند. به عبارت دیگر، مجموع اختلاف اعداد جوراب‌های جفت شده کمینه شود (رادزینکا از اختلاف زیاد اعداد جوراب‌هایش ناراحت می‌شود) از آن‌جایی که مادر رادزینکا مشغول تمیز کردن خانه است،‌ زمان کافی برای جفت کردن جوراب‌ها با شرایط دلخواهش را ندارد. به او کمک کنید تا این کار را انجام دهد. # ورودی در خط اول ورودی عدد $n$ آمده است که نشان‌دهنده تعداد لنگه جوراب‌های موجود در اتاق رادزینکا است. در خط دوم $n$ عدد آمده است که $i$ امین عدد نشان‌دهنده رنگ‌ جورابی است که بر روی آن عدد $i$ نوشته شده است. $$1 \le n \le 200$$ رنگ جوراب‌ها عددی بین ۱ تا ۱۰۰ است. # خروجی در اولین خط خروجی عدد $k$ را خروجی دهید که نشان‌دهنده بیشینه تعداد جفت‌هاست. در $i$امین خط از $k$ خط بعدی به ترتیب دو عدد $a$ و $b$ را خروجی دهید که نشان‌دهنده اعداد جوراب‌هایی است که مادر رادزینکا در مرحله $i$ام جفت می‌کند. دقت کنید که $a$ کوچکتر از $b$ باشد. همچنین به‌خاطر وسواس مادر رادزینکا در برقراری نظم و ترتیب، جفت‌ها را طوری خروجی دهید که بر اساس عدد کوچکتر، مرتب شده باشند. یعنی اگر جفت $x$ قبل از جفت $y$ ظاهر شده است، جورابی که در بین چهار لنگه این دو جفت شماره کمینه را دارد، در جفت $x$ باشد. # مثال ## ورودی نمونه ۱ ``` 5 1 2 1 2 3 ``` ## خروجی نمونه ۱ ``` 2 1 3 2 4 ``` ## ورودی نمونه ۲ ``` 8 1 4 1 1 4 1 4 1 ``` ## خروجی نمونه ۲ ``` 3 1 3 2 5 4 6 ```

حل سؤال در بانک سؤالات