Менеджеры памяти – части операционных систем и систем программирования, управляющие выделением, освобождением и распределением памяти. Самый низкий уровень менеджеров оперирует страницами физической памяти – унифицированными блоками одинаковой длины, на которые разбивается всё доступное адресное пространство.

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

1. Первоначально у менеджера $$$n$$$ свободных страниц, пронумерованных от $$$0$$$ до $$$n - 1$$$.
2. Менеджер умеет выделять страницы только по одной. В результате выделения страница становится занятой и не выделяется повторно.
3. Каждый $$$i$$$-й запрос на выделение содержит номер предпочитаемой страницы $$$h_i$$$ – той, которую желали бы получить.
4. Если предпочитаемая страница с номером $$$h_i$$$ свободна, то менеджер выделяет именно её.
5. Если предпочитаемая страница занята, то выделяется ближайшая свободная $$$r_i$$$, с минимальной разницей $$$|r_i - h_i|$$$. Если таких страниц 2, то выбирается страница с меньшим номером $$$r_i$$$.
6. Выделив страницу, менеджер помечает её как занятую и возвращает её номер $$$r_i$$$ в качестве ответа на запрос.
7. Предполагается, что у менеджера достаточно свободных страниц, чтобы удовлетворить все поступающие запросы.