Python.Multiset

# импортируем нужные функции
from bisect import bisect_left, bisect_right, insort_left, insort_right


class Multiset:
    def __init__(self, iterable=None):
        # конструктор
        if iterable is None:
            self.__dataset = []  # пустое множество
        else:
            self.__dataset = [e for e in iterable]  # перекидываем данные
            self.__dataset.sort()  # поддерживаем отсортированность

    def insert(self, item):
        # добавить элемент
        self.insert_right(item)

    def insert_right(self, item):
        # вставить элемент как можно правее
        insort_right(self.__dataset, item)

    def insert_left(self, item):
        # вставить элемент как можно левее
        insort_left(self.__dataset, item)

    def erase(self, item):
        # у-да-лить
        self.erase_right(item)

    def erase_all(self, item):
        # удалить все такие элементы
        left = self.__left_index_or_none(item)
        right = self.__right_index_or_none(item)
        del self.__dataset[left: right + 1]  # левая граница в сделку не входила

    def erase_right(self, item):
        # удаляем правый элемент (нафик из этой жизни, блин)
        i = self.__right_index_or_none(item)
        if i:
            del self.__dataset[i]
        else:
            raise ValueError("No such item in set!")

    def erase_left(self, item):
        # удаляем левый элемент
        i = self.__left_index_or_none(item)
        if i:
            del self.__dataset[i]
        else:
            raise ValueError("No such item in set!")

    def pop(self, item):
        return self.pop_right(item)

    def pop_left(self, item):
        i = self.__left_index_or_none(item)
        if i is None:
            # падаем скорей!! (главное правило программирования)
            raise ValueError("No such item in set!")
        v = self.__dataset[i]  # запоминаем, что надо вернуть
        del self.__dataset[i]  # удаляем эту пакость
        return v

    def pop_right(self, item):
        i = self.__right_index_or_none(item)
        if i is None:
            raise ValueError("No such item in set!")
        v = self.__dataset[i]
        del self.__dataset[i]
        return v

    def lower(self, item):
        i = self.__left_index_or_none(item)
        if i is None:
            raise ValueError("No such item in set!")
        return self.__dataset[i]

    def upper(self, item):
        i = self.__right_index_or_none(item)
        if i is None:
            raise ValueError("No such item in set!")
        return self.__dataset[i]

    def count(self, item):
        # кол-во элементов: len([l; r]) = r - l + 1
        left = self.__left_index_or_none(item)
        right = self.__right_index_or_none(item)
        if left is None or right is None:
            return 0
        return right - left + 1

    def max(self):
        return self.__dataset[-1]

    def min(self):
        return self.__dataset[0]

    def count_of_greater_than(self, item):
        return self.__dataset.__len__() - bisect_right(self.__dataset, item)

    def count_of_less_than(self, item):
        return bisect_left(self.__dataset, item)

    def __right_index_or_none(self, item):
        # вспомогательный метод: ищет самый правый элемент
        i = bisect_right(self.__dataset, item) - 1
        if i >= 0 and self.__dataset[i] == item:
            return i
        return None

    def __left_index_or_none(self, item):
        # вспомогательный метод: ищет самый левый элемент
        i = bisect_left(self.__dataset, item)
        if i != len(self.__dataset) and self.__dataset[i] == item:
            return i
        return None

    def __len__(self):
        # сколько элементов во множестве
        return self.__dataset.__len__()

    def __iter__(self):
        # итератор, чтобы можно было проходится по элементам в цикле for
        return self.__dataset.__iter__()

    def __contains__(self, item):
        # item in self.dataset; проверяет, есть ли значение во множестве
        return self.__left_index_or_none(item) is not None

    def __str__(self):
        # возвращает красивое строковое представление объекта
        return self.__dataset.__str__()