PriorityQueuePair

template <typename T, typename Cmp = std::less<T>>
struct PriorityQueuePair {
  Cmp cmp;
  std::priority_queue<T, std::vector<T>, Cmp> data;
  std::priority_queue<T, std::vector<T>, Cmp> kill;

  PriorityQueuePair(const Cmp& _cmp = Cmp {}) : cmp(_cmp), data(cmp), kill(cmp) {
    void(0);
  }

  void normalize() {
    while (!kill.empty()) {
      if (kill.top() == data.top()) {
        kill.pop();
        data.pop();
      } else {
        assert(cmp(kill.top(), data.top()));
        break;
      }
    }
  }

  void insert(const T& x) {
    data.push(x);
  }

  void erase(const T& x) { // x should exist.
    kill.push(x);
    assert(int(data.size()) >= int(kill.size()));
    normalize();
  }

  [[nodiscard]] const T& get() const {
    assert(!data.empty());
    return data.top();
  }

  [[nodiscard]] int size() const {
    return int(data.size() - kill.size());
  }

  [[nodiscard]] bool empty() const {
    return size() == 0;
  }
};