static size_t ID {0};
template <typename T>
class PriorityCollection {
public:
    using Id = size_t/* тип, используемый для идентификаторов */;

    // Добавить объект с нулевым приоритетом
    // с помощью перемещения и вернуть его идентификатор
    Id Add(T object) {
        p.insert({0, ID});
        data.insert({ID++, move(object)});
        return ID;
    }

//    Добавить все элементы диапазона [range_begin, range_end)
//    с помощью перемещения, записав выданные им идентификаторы
//    в диапазон [ids_begin, ...)
    template <typename ObjInputIt, typename IdOutputIt>
    void Add(ObjInputIt range_begin, ObjInputIt range_end,
             IdOutputIt ids_begin) {
        for (auto it = range_begin; it != range_end; it++) {
            *ids_begin = Add(move(*it));
        }
}

    // Определить, принадлежит ли идентификатор какому-либо
    // хранящемуся в контейнере объекту
    bool IsValid(Id id) const {
        for (const auto& i : p) {
            if (i.second == id) {
                return true;
            }
        }
        return false;
    }

    // Получить объект по идентификатору
    const T& Get(Id id) const {
        for (auto& item : data) {
            if (item.first == id) {
                return item.second;
            }
        }
    }

    // Увеличить приоритет объекта на 1
    void Promote(Id id) {
//        for (auto it = p.begin(); it != p.end();)
//
        for (auto& item : p) {
            if (item.second == id) {
                auto temp = item;
                p.erase(item);
                temp.first++;
                p.insert(temp);
                break;
            }
        }
    }

    // Получить объект с максимальным приоритетом и его приоритет
    pair<const T&, int> GetMax() const {
        auto item1 = *prev(p.end());
        return {Get(item1.second), item1.first};
    }

    // Аналогично GetMax, но удаляет элемент из контейнера
    pair<T, int> PopMax() {
        pair<int, Id> item = *prev(p.end());
        p.erase(prev(p.end()));
        auto it_to_delete = data.begin();
        for (auto it = data.begin(); it != data.end(); it++) {
            if (it->first == item.second) {
                it_to_delete = it;
                break;
            }
        }
        pair<T, int> res;
        res = make_pair(move(it_to_delete->second), item.first);
        data.erase(it_to_delete);
        return move(res);
    }

private:
    set<pair<int, Id>> p;
    set<pair<Id, T>> data;
};