We are given a vector $\mathbf{b}$ of size $h$. Initially we have $\mathbf{b}_i=1$ for all $i\in \{1, 2, \ldots, h\}$. In a sequential fashion, at each time step $t=1, \ldots, n$, an index $j(t)$ is (adversarially) selected from $\{1, 2, \ldots, h\}$, $\mathbf{b}_{j(t)}$ is incremented by $1$, and the only information we receive is index $j(t)$.
We are also given a vector of integers $\mathbf{a}$ of size $h$. Our goal is to maintain over time vector $\mathbf{a}$, such that, at each time step for all $i\in \{1, 2, \ldots, h\}$ we have that $\mathbf{a}_i$ is equal to $\sum_{k=1}^i \mathbf{b}_k$ up to a constant factor (even a logarithmic factor in $n$ or $h$ would be acceptable). Initially (at time step $0$) each integer $\mathbf{a}_i$ is set to be equal to $\sum_{k=1}^i \mathbf{b}_k$ which in turn is equal to $i$.
Question: How can we build an algorithmic (possibly randomized) strategy to maintain over time vector $\mathbf{a}$ with a total (expected if randomized) number of elementary operations (i.e., the algorithmic time complexity) equal to $\mathcal{O}(n\log n)$ (or, if possible, $\mathcal{O}(n)$)?
