Insert, delete and get random in O(1) with duplicates

Design a collection of integers that allows duplicates and supports, each in average O(1) time:

1. insert(val): add one copy of val; return whether val was absent before.
2. remove(val): remove one copy of val if present; return whether anything was removed.
3. get_random(): return a random element, where each value's chance is proportional to how many copies of it the collection holds.

Explain the array-plus-index-map layout and how you remove from the middle of the array in constant time.