Java Straightforward Solution, O(n) time, O(1) space
\nclass RLEIterator {\n    int index;\n    int [] A;\n    public RLEIterator(int[] A) {\n        this.A = A;\n        index = 0;\n    }\n    \n    public int ne
```\nclass RLEIterator {\n    int index;\n    int [] A;\n    public RLEIterator(int[] A) {\n        this.A = A;\n        index = 0;\n    }\n    \n    public int next(int n) {\n        while(index < A.length && n > A[index]){\n            n = n - A[index];\n            index += 2;\n        }\n        \n        if(index >= A.length){\n            return -1;\n        }\n        \n        A[index] = A[index] - n;\n        return A[index + 1];\n    }\n}\n```\nNote: input array doesn\'t count as extra space. I would say this problem is a O(n) space problem, but the solution I use is only O(1) space, since I didn\'t allocate any extra space.
[]