We can use run-length encoding (i.e., RLE) to encode a sequence of integers. In a run-length encoded array of even length encoding (0-indexed), for all even i, encoding[i] tells us the number of times that the non-negative integer value encoding[i + 1] is repeated in the sequence.


	For example, the sequence arr = [8,8,8,5,5] can be encoded to be encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] and encoding = [2,8,1,8,2,5] are also valid RLE of arr.


Given a run-length encoded array, design an iterator that iterates through it.

Implement the RLEIterator class:


	RLEIterator(int[] encoded) Initializes the object with the encoded array encoded.
	int next(int n) Exhausts the next n elements and returns the last element exhausted in this way. If there is no element left to exhaust, return -1 instead.


&nbsp;
Example 1:

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

Explanation
RLEIterator rLEIterator = new RLEIterator([3, 8, 0, 9, 2, 5]); // This maps to the sequence [8,8,8,5,5].
rLEIterator.next(2); // exhausts 2 terms of the sequence, returning 8. The remaining sequence is now [8, 5, 5].
rLEIterator.next(1); // exhausts 1 term of the sequence, returning 8. The remaining sequence is now [5, 5].
rLEIterator.next(1); // exhausts 1 term of the sequence, returning 5. The remaining sequence is now [5].
rLEIterator.next(2); // exhausts 2 terms, returning -1. This is because the first term exhausted was 5,
but the second term did not exist. Since the last term exhausted does not exist, we return -1.


&nbsp;
Constraints:


	2 &lt;= encoding.length &lt;= 1000
	encoding.length is even.
	0 &lt;= encoding[i] &lt;= 109
	1 &lt;= n &lt;= 109
	At most 1000 calls will be made to next.


class RLEIterator:

    def __init__(self, encoding: List[int]):
        self.encoding = encoding

    def next(self, n: int) -> int:

        if self.encoding:

            count = self.encoding[0]

            if count >= n:
                # Partially exhaust and return the current value.
                self.encoding[0] -= n
                return self.encoding[1]

            # Exhaust all of current value and continue.
            self.encoding = self.encoding[2:]
            return self.next(n - count)

        return -1
class RLEIterator {
    
    long[] prefixEncoded;
    long processed = 0;
    int l = 0;

    public RLEIterator(int[] encoding) {
        int encodeLen = encoding.length;
        this.prefixEncoded = new long[encodeLen];
        for(int i=0;i<encodeLen;i+=2) {
            long prevPrefixSum = 0;
            if(i > 0) {
                prevPrefixSum = this.prefixEncoded[i-2];
            }
            this.prefixEncoded[i] = encoding[i] + prevPrefixSum;
            this.prefixEncoded[i+1] = encoding[i+1];
        }
    }

    public int next(int n) {
        int r = this.prefixEncoded.length-2;
    
        processed += n;
        
        if(l >= this.prefixEncoded.length || processed > this.prefixEncoded[this.prefixEncoded.length - 2]) {
            return -1;
        }
        
        while(l < r) {
            int m = (l + ((r-l)/2));
            if(m % 2 != 0) {
                m = m - 1;
            }
            if(this.prefixEncoded[m] >= processed) {
                r = m;
            } else {
                l = m + 2;
            }
        }
        return l >= this.prefixEncoded.length ? -1: (int) this.prefixEncoded[l + 1];
    }   
}
/*
    https://leetcode.com/problems/rle-iterator/
    
    next(): TC: O(n) in total over n calls
    Idea is to use two pointers are this.
    We maintain a ptr that points to the current element bucket. For a given n
    first iterate through the buckets which have freq < n, this means they won't have the 
    last element.
    Once the iteration ends, either we will have no elements left or we will be on the bucket
    with freq >= n. Update the iteration ptr accordingly.
*/
class RLEIterator {
    vector<int> encoding;
    // Tracks the even indices
    int curr = -1;
    // Tracks the total length of array
    int len = 0;
public:
    RLEIterator(vector<int>& encoding) {
        this->encoding = encoding;
        curr = 0;
        len = encoding.size();
    }
    
    int next(int n) {
        // Skip all the number buckets which will be completely exhausted
        // and we will still have some n left i.e n > 0
        for(; curr < len && n > 0 && encoding[curr] < n; curr += 2) {
            // Skip the buckets with 0 frequency
            if(encoding[curr] == 0)
                continue;
            n -= encoding[curr];
        }
        
        int element = -1;
        //  If we still have elements left with non zero frequency then
        // the current bucket's frequency will be >= leftover n
        if(curr < len && encoding[curr] >= n) {
            // Exhaust the leftover n
            encoding[curr] -= n;
            element = encoding[curr+1];
            // If the bucket is completely exhausted, then move the iterator ptr to next element
            // for the next function call
            if(encoding[curr] == 0)
                curr += 2;
        }
        return element;
    }
};

/**
 * Your RLEIterator object will be instantiated and called as such:
 * RLEIterator* obj = new RLEIterator(encoding);
 * int param_1 = obj->next(n);
 */
var RLEIterator = function(encoding) {
    this.encoding = encoding
    // Pointer to count index
    this.index = 0
}

RLEIterator.prototype.next = function(n) {
    while (n > 0) {
        // Move to next count index when the current index is 0
        if (this.encoding[this.index] === 0) this.index += 2
        
        // Too many calls to next, return -1
        if (this.index >= this.encoding.length) return -1
        
        // n goes completely into count
        if (n <= this.encoding[this.index]) {
            this.encoding[this.index] -= n
            n = 0
        // count goes completely into n
        } else if (n > this.encoding[this.index]) {
            n -= this.encoding[this.index]
            this.encoding[this.index] = 0
        }
    }

    return this.encoding[this.index + 1]
}
RLE Iterator