Дневник: самая длинная неделя с K предметами

В школе завуч проверяет дневники. За каждый день в дневнике записан номер предмета, который был последним уроком в этот день.

Завуч хочет найти самый длинный подряд идущий отрезок дней, в котором встречается не больше K разных предметов. Если таких отрезков несколько, завуч выбирает тот, у которого левый конец минимальный. Если и он одинаковый — тот, у которого правый конец минимальный.

Найдите выбранный отрезок.

Формат ввода

Первая строка: два целых числа n и k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 5000). Вторая строка: n целых чисел a1, a2, ..., an — номера предметов (1 ≤ ai ≤ 1000000).

Формат вывода

Выведите три числа: len l r, где len — длина найденного отрезка, а l и r — его границы (нумерация дней с 1).

Ограничения

• 1 ≤ n ≤ 5000
• 1 ≤ k ≤ 5000
• 1 ≤ ai ≤ 1000000

Пример

Ввод:

10 2
1 2 1 3 4 3 3 4 4 4

Вывод:

7 4 10

Здесь лучший отрезок — дни 4..10: предметы {3,4}, длина 7.

Ключевое наблюдение: нам нужен самый длинный подряд идущий отрезок, где количество разных значений ≤ K. Если мы знаем текущий отрезок [l..r] и добавляем день r+1, то «плохим» он станет только из‑за появления нового предмета. Значит, можно поддерживать окно и чинить его, двигая только левую границу.

Приём: скользящее окно (два указателя). Правый указатель r идёт слева направо, а левый l двигается только вперёд, пока условие (разных ≤ K) снова не выполнится. Это работает, потому что при фиксированном r минимальный l, делающий окно корректным, находится монотонно: l никогда не нужно откатывать назад.

План:

• Завести словарь cnt[предмет] = сколько раз в окне и число distinct (сколько разных в окне).
• Идти r от 0 до n-1:
• добавить a[r]: увеличить cnt, если предмет новый — увеличить distinct.
• пока distinct > k: убрать a[l] (уменьшить cnt; если стало 0 — удалить и уменьшить distinct), затем l += 1.
• теперь окно [l..r] корректно; обновить лучший ответ.
• Для выбора при равной длине применить сравнение: больше длина; если равна — меньше l; если и l равны — меньше r.

Сниппет длины окна: cur_len = r - l + 1.

Сложность: O(n) шагов указателей, операции со словарём амортизированно O(1), итого O(n).

Частая ошибка: неправильно обработать момент, когда частота стала 0 (забыть уменьшить distinct и/или удалить ключ) — тогда цикл while distinct > k может работать неверно и ответ «съедет».