We are given a sequence $ b_1, b_2, ldots, b_h $ container, where each container initially contains $ 1 $ ball. Sequentially, at each time step $ t = 1, ldots, n $, a ball is thrown into a ** adversarially selected** compartment $ b_ {j (t)} $, and we are informed about the bin index $ j (t) $. Assuming that each container is a set, we denote by $ | b_i | $ the number of balls contained in the container $ b_i $.

They also give us a series of integers $ A (i) $ for $ i in {1, 2, ldots, h } $, and we assume to have access to each record of $ A ( cdot) $ as well as read and modify it in constant time. In time $ 0 $ each integer $ A (i) $ is equal to $ i $.

Our goal is to maintain ** overtime** $ A ( cdot) $so that for everyone $ i in {1, 2, ldots, h } $,

**we have that $ A (i) $ is equal to $ sum_ {k = 1} ^ i | b_k | $**

*at every step of time***(even a**

*up to a constant factor**logarithmic factor in $ n $ or $ h $*It would be acceptable).

**Question:** How can we build an algorithmic (*possibly randomized*) strategy to maintain ** overtime** the array of integers $ A ( cdot) $ with a

**(**

*total**expected*if randomized) number of elementary operations (i.e. algorithmic time complexity) equal to $ mathcal {O} (n log n) $ (or, if possible, $ mathcal {O} (n) $) while the above restriction is met?