sclass OptimizedMultiSet<A> {
  new Map<A, Int> map;
  new MultiSetMap<Int, A> byCount;
  int size;
  
  int add(A a) {
    size++;
    Int i = map.get(a), count;
    if (i != null)
      byCount.remove(i++, a);
    else
      i = 1;
    map.put(a, i);
    byCount.add(i, a);
    ret i;
  }
  
  void remove(A a) {
    Int i = map.get(a);
    if (i != null) {
      --size;
      byCount.remove(i, a);
      if (--i > 0) {
        map.put(a, i);
        byCount.add(i, a);
      } else
        map.remove(a);
    }
  }
  
  bool isEmpty() {
    ret map.isEmpty();
  }
  
  toString {
    ret str(map);
  }
}