Перли і конвертер#10301
Перли — це мирна і давня раса, яка через вину людства майже зникла, а її залишки дрейфували у космосі. Прибувши на Альфу, перли познайомилися з Валеріаном і Лорелін і отримали конвертер перлин.
Конвертер — це мила істота, яка виробляє перлини різних кольорів. Для запуску двигуна космічного корабля перлам потрібен набір із різнокольорових перлин. Конвертер виробляє одну перлину на секунду. Для ефективної роботи двигуна потрібно, щоб у кожному наборі для будь-якої пари перлин виконувалася умова: різниця в часі між появою цих перлин не перевищує секунд. Кожна перлина може входити лише до одного набору.
Конвертер створив перлин і втомився. Допоможіть перлам визначити найбільшу можливу кількість наборів перлин, які вони зможуть скласти з отриманих перлин.
У першому рядку записано три цілих числа , , — кількість перлин, створених конвертером; максимальний проміжок часу між появою кожної пари перлин в одному наборі; та кількість різних кольорів перлин відповідно (1 \le m \le n \le 10^5, 1 \le k \le 10^5).
У наступному рядку міститься цілих чисел a_{i} — колір -ї перлини, що з’явилася (1 \le a_i \le k).
У першому рядку виведіть одне число — найбільшу можливу кількість наборів перлин, які перли можуть скласти з наявних перлин.
У наступних рядках виведіть по цілих чисел d_{ij} — номери перлин, що входять до -го набору (1 \le d_{ij} \le n).
Якщо правильних відповідей кілька, виведіть будь-яку з них.
Приклад 1
Приклад 2
Приклад 3
Ця задача містить п’ять підзадач. Для підзадач діють додаткові обмеження, наведені нижче. Для отримання балів за підзадачу необхідно пройти всі тести даної підзадачі, а також всі тести всіх необхідних підзадач. Номери необхідних підзадач також зазначено в таблиці.
( балів): n = m, n \le 1000;
( балів): k = 2, n \le 1000;
( балів): k \le 10, n \le 1000;
( балів): n \le 1000;
( балів): повні обмеження.