1
class RLEIterator {
2

3
  long[] prefixEncoded;
4
  long processed = 0;
5
  int l = 0;
6

7
  public RLEIterator(int[] encoding) {
8
    int encodeLen = encoding.length;
9
    this.prefixEncoded = new long[encodeLen];
10
    for (int i = 0; i < encodeLen; i += 2) {
11
      long prevPrefixSum = 0;
12
      if (i > 0) {
13
        prevPrefixSum = this.prefixEncoded[i - 2];
14
      }
15
      this.prefixEncoded[i] = encoding[i] + prevPrefixSum;
16
      this.prefixEncoded[i + 1] = encoding[i + 1];
17
    }
18
  }
19

20
  public int next(int n) {
21
    int r = this.prefixEncoded.length - 2;
22

23
    processed += n;
24

25
    if (l >= this.prefixEncoded.length
26
        || processed > this.prefixEncoded[this.prefixEncoded.length - 2]) {
27
      return -1;
28
    }
29

30
    while (l < r) {
31
      int m = (l + ((r - l) / 2));
32
      if (m % 2 != 0) {
33
        m = m - 1;
34
      }
35
      if (this.prefixEncoded[m] >= processed) {
36
        r = m;
37
      } else {
38
        l = m + 2;
39
      }
40
    }
41
    return l >= this.prefixEncoded.length ? -1 : (int) this.prefixEncoded[l + 1];
42
  }
43
}