Approach 1: Store Exhausted Position and Quantity
We can store an index
i and quantity
q which represents that
q elements of
A[i+1] times) are exhausted.
For example, if we have
A = [1,2,3,4] (mapping to the sequence
i = 0, q = 0 represents that nothing is exhausted;
i = 0, q = 1 represents that
 is exhausted,
i = 2, q = 1 will represent that we have currently exhausted
[2, 4], and so on.
Say we want to exhaust
n more elements. There are currently
D = A[i] - q elements left to exhaust (of value
n > D, then we should exhaust all of them and continue:
n -= D; i += 2; q = 0.
Otherwise, we should exhaust some of them and return the current element's value:
q += D; return A[i+1].
Time Complexity: , where is the length of
A, and is the number of calls to
Space Complexity: .
Analysis written by: @awice.