Симпатичные последовательности

Рассмотрим последовательность a₁, a₂, ..., a_n неотрицательных целых чисел. Обозначим как c_i,j количество появлений числа i среди чисел a₁, a₂, ... , a_j. Будем называть последовательность k-симпатичной, если для всех i₁ < i₂ и для всех j выполнено условие: c_i1,j ≥ c_i2,j − k.

По заданной последовательности a₁, a₂, ..., a_n и числу k, найдите ее максимальный префикс, который является k-симпатичным.

Входные данные

Первая строка входного файла INPUT.TXT содержит числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 200 000). Вторая строка содержит n целых чисел в диапазоне от 0 до n.

Выходные данные

В выходной файл OUTPUT.TXT выведите максимальное p такое, что последовательность a₁, a₂, ..., a_p является k-симпатичной.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]