Java Prefix Sum + Binary Search, O(logn) next
First we do prefix sum of all available items in the new array A.\nIn each call, we find the smallest index, where the number of elements is enough to cover our
First we do prefix sum of all available items in the new array `A`.\nIn each call, we find the smallest index, where the number of elements is enough to cover our query. \nLeft boundry of binary search keeps getting closer to the end at each call. \n\nClassic binary search diffs:\n`& ~1` drops the last bit for each number, this way we always look at the number of items, not the item.\n`l = m + 2` to go to next next item count\n\nTime:\n`Init - O(N)`\n`next - O(logN)`\n\nSpace:\n`O(N)`\n```\nclass RLEIterator {\n    \n    long [] A;\n    long taken = 0;\n    int l = 0;\n\n    public RLEIterator(int[] encoding) {\n        this.A = new long[encoding.length];\n        for(int i = 0; i < encoding.length ; i += 2) {\n            this.A[i] = encoding[i] + (i > 0 ?  A[i - 2] : 0);\n            this.A[i + 1] = encoding[i + 1];\n        }\n    }\n\n    public int next(int n) {\n        taken += n;\n        if(l >= A.length || taken > A[A.length - 2]) {\n            return -1;\n        }\n        int r = A.length - 2;\n        while(l < r) {\n            int m = ((r - l) / 2 + l) & ~1;\n            if(A[m] >= taken) {\n                r = m;\n            } else {\n                l = m + 2;\n            }\n        }\n        return l >= A.length ? -1: (int) A[l + 1];\n    }   \n}\n```
[]