This doesn't seem to be O(1) on removing.
Removing sets #shouldArrange which then means a call to #arrange which is clearly not O(1).
The readme file in the repo itself says that it is O(n) in adding and removing and O(1) only in searching.
It also should be mentioned that it needs an additional O(n) space. I mean, if you need a certain structure for performance you most likely need to consider the cost, so I would think this should be mentioned in the readme.