Insertion into a sorted list, in constant time

Question

I have a sorted list of integers, and I wish to insert into this list any element, in constant time. I'm allowed to do some pre-processing, as long as it will let me run this operation in constant time (i.e., no matter how many times I repeat this operation after the pre-processing, it should run in constant time).

How can this be done?

Edit : I can think of a couple of more constraints to make it a bit less ambiguous, and a bit more challenging to solve -

1. list needs to be maintained in sorted order post-insertion(s)
2. Or, list needs to somehow support max/min operations in constant time post insertion(s).

Answer 1

You can put the integers into a radix tree, treating the integers as bit strings. With a radix of 2 and a list of 32-bit integers you'll have a maximum tree depth of 32, which is your constant factor for constant-time insertion (you wouldn't ordinarily do something like this because the constant factor for the radix tree is probably going to be larger than the log factor of a balanced binary tree, plus all of the bit twiddling you'll need to do in for the radix tree is going to be costly)