You might wish to use an auxillary array of size at most 4
n
.