Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 61%)

Рассмотрим последовательность a1, a2, ..., an неотрицательных целых чисел. Обозначим как ci,j количество появлений числа i среди чисел a1, a2, ... , aj. Будем называть последовательность k-симпатичной, если для всех i1 < i2 и для всех j выполнено условие: ci1,j ≥ ci2,j − k.

По заданной последовательности a1, a2, ..., an и числу k, найдите ее максимальный префикс, который является k-симпатичным.

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

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

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

В выходной файл OUTPUT.TXT выведите максимальное l такое, что последовательность a1, a2, ..., al является k-симпатичной.

Примеры

INPUT.TXTOUTPUT.TXT
110 1
0 1 1 0 2 2 1 2 2 3
8
22 0
1 0
0

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru