Маленький Артёмка изобрёл машину времени! Он может перемещаться во времени куда угодно, но, разумеется, все его мысли только о программировании. Он хочет использовать машину времени, чтобы улучшить известную структуру данных — мультимножество.
Артёмка хочет создать простое мультимножество для целых чисел. Он хочет поддерживать следующие операции:
- Добавить целое число в мультимножество. Обратите внимание, что разница мультимножества и множества состоит как раз в том, что в мультимножестве одно и то же число может содержаться несколько раз.
- Удалить целое число из мультимножества. При этом удаляется только одно вхождение числа в мультимножество. Артёмка не хочет иметь дело с разными исключениями, так что все операции удаления применяются только в случае, если хотя бы один экземпляр числа присутствует в мультимножестве.
- Узнать, сколько экземпляров данного целого числа находится в мультимножестве.
Но что же насчёт машины времени? Если обычно Артёмка просто выполняет последовательность операций со своим мультимножеством, то теперь он умеет перемещаться в произвольные моменты времени и добавлять там новые операции! Давайте посмотрим на пример.
- Сперва Артёмка добавляет число 5 в мультимножество в момент времени 1.
- Затем он добавляет число 3 в мультимножество в 5-й момент времени.
- В момент времени 6 Артёмка спрашивает, сколько 5 содержится в мультимножестве. Ответ — 1.
- Затем Артёмка возвращается назад во времени и спрашивает, сколько чисел 3 было в мультимножестве в момент времени 4. Так как 3 была добавлена только в момент времени 5, то ответ на запрос Артёмки — 0.
- Затем Артёмка снова возвращается назад во времени и удаляет 5 из мультимножества в момент времени 3.
- Наконец, в момент времени 7 Артёмка спрашивает, сколько 5 содержится в мультимножестве. Ответ — 0, так как мы добавили одну 5 в момент времени 1 и удалили её в момент времени 3.
Заметьте, что Артёмка настолько не любит исключения, что после любой его последовательности действий операции добавления и удаления остаются корректными, то есть никогда не поступает запрос на удаление несуществующего элемента. Ответом на запрос третьего типа является количество вхождений элемента в момент, когда Артёмка обращается к мультимножеству, то есть дальнейшие действия Артёмки не влияют на ответ на данный запрос.
Помогите Артёмке реализовать мультимножество для путешественников во времени.