Кеширующий сервер

[Dimpa]

Код на C# или Java
Дормидонт работает в компании, которая занимается обработкой
больших данных.
Обрабатываемые данные находятся где-то в распределенной
системе.
Количество различных данных в системе ограничено и каждое
данное имеет свой номер.
Эти данные регулярно требуются различным
клиентам и, поскольку время обращения к ним достаточно велико, для
ускорения обработки информации Дормидонту поручено написать часть
middlware — сервер-посредник, к которому и обращаются теперь клиенты за
данными. Так как система — распределенная, а сервер — нет, все требуемые
данные на сервер не помещаются, но он имеет возможность запоминать
результаты своих запросов к распределенной системе. Для этого на сервере
выделена ограниченная память на N запросов. Важно, что клиент не имеет
возможности обращаться к распределенной системе и результат запроса к
распределенной системе всегда должны оказаться на сервере.

К большой радости Дормидонта оказалось, что самые крупные и
значимые клиенты всегда обращаются за одними и теми же данными в одном
и том же порядке, так что у него есть последовательность запросов. Дормидонт
придумал такой алгоритм, что как можно большее количество запросов
исполняется из кеша сервера, без обращения к распределенной системе.

Придумаете ли вы что-то подобное?

Формат входных данных:

На вход программы подается размер памяти под кеширование запросов
1 ≤ N ≤ 100000, количество запросов 1 ≤ M ≤ 100000 и ровно M запросов с
номерами 0 ≤ Ri ≤ 1018 . Количество различных номеров запросов ограничено
и не превосходит 100000.

Формат выходных данных:

Требуется вывести одно число: сколько раз пришлось обратиться к
распределенной системе за данными, отсутствующими в кеше. В начале
работы кеш пуст


Замечание
В приведенном примере первые три запроса произойдут к данным под
номерами 3, 1 и 4, так как их нет в кеше. Следующий запрос, 1, есть в кеше и
обращения к распределенной системе не произойдет. Запросы 5 и 9 занесут их
в кеш. Следующий запрос — 2 — в кеше отсутствует, но мы выкинем из кеша
запрос 1 и запрос 2 займет его место. Далее, запрос 6 вытеснит из кеша
значение 2(у нас есть информация о дальнейших запросах и из нее мы видим,
что запрос под номером 2 больше не повториться и нет причин хранить его
далее), после чего следующие три запроса удовлетворятся из кеша. Затем
произойдет еще два вытеснения — 8 и 7. Итого 9 обращений к распределенной
системе. Нетрудно установить, что меньше сделать нельзя.