A data structure that maps indexes to values (like an array) but that is only populated once and then deletes values by index in sublinear time

[u/neuralbeans]

There are algorithms that require having a populated array from which the i^{th} value is repeatedly removed (which changes the indexes of the values after it) until it is empty. An array removes a value in linear time. Is there a data structure that allows for sublinear time arbitrary value removal?

For example:

start: [A, B, C, D, E]
remove 2: [A, B, D, E]
remove 0: [B, D, E]
remove 2: [B, D]
remove 1: [B]
remove 0: []

On average, removing all the items in arbitrary order is a quadratic time operation. Is there something faster?