Java Solution: With detailed explanation
Approach\nIf we expand the sequence and store them in a temporary datastructure like LinkedList.  Then we can return the elements as and when the next() gets ca
# Approach\nIf we expand the sequence and store them in a temporary datastructure like LinkedList.  Then we can return the elements as and when the next() gets called.  For example: [3,8,0,9,2,5] gets expanded and stored as 3 times 8, 0 times 9 and 2 times 5 i.e., [8,8,8,5,5].  When next() gets called with n = 2, remove first 2 elements from the array from front and return the last element.   \n# Optimization\nThe above approach works well, but the problem is when the run length of a sequence is high as mentioned in the problem statement(10^9), then the space usage will also be high.  If we check the above approach carefully we actually don\'t need this new linkedList(or stack or any other) data structure.  We only need to maintain the currentElement and the remaining run length of that  element.  Hence, the new approach with optimization is given below.\n# Algorithm\n1.  Store the incoming sequence as it is.  Maintain the state of the current run length and element as mentioned below.\n\t\t\ti.  int A[] // input sequence.\n\t\t\tii.  currentNum = -1 // Current element to return as part of next()\n\t\t\tiii.  runLen = 0  // run length of currentNum\n\t\t\tiv.  nextIdx = 0 // next index of the currentNum.\n2.  When next() gets called with n.\n     1.  Case1:  Can we accomodate n with existing runLenght? Check if n <= remainingRunLength.  If yes then update remainingRunLength by subtracting n from it.\n     2.  Case2:  If we are at the end of the sequence ?  Check if nextIdx >= A.length.  If yes then its not possible to continue further.  So, at this point our output can be only 2 values either -1 or the currentNum.  If runLength != 0 then the last exhaust Number will be -1 otherwise it\'ll be curretNum(which was set in previous call to next(), and it can be either -1 or some valid number).  So, return that.\n     3.  Case3:  Iterate over the Seq using nextIdx.  Remember nextIdx should be incremented by 2 as A[i] is the runLength and A[i+1] is the actual number.  It\'s guaranteed that length of sequence A is always even.  So, it\'s ok to increment twice in the loop and update the current runLength and currentNumber.  Also, keep updating the n by subtracting runLength from n.  This helps solve when n spans across multiple sequence. \n     4.  Case3 continued:  After we exit while loop check if n is still greater than zero.  This is because during last runLength updated, runLength grew beyond n, hence we came out of while loop.  So, check if n > 0 then update the runLength accordingly and return the output. Code is given below.\n3.  Run Time Complexity O(N) --> N sequence length.  Space complexity is constant.  We can probably optimize space complexity by removing one or two variables but it takes away the readability and doesn\'t give any major improvements.  \n4.  Please feel free to comment.  Thank you \n# Code\n```\nclass RLEIterator {\n    int runLen ;\n    int currentNum  ;\n    int[] A ;\n    int nextIdx ;\n   \n    public RLEIterator(int[] A) {\n        this.A = A; // Store the sequence as it is\n        this.nextIdx = 0 ; // nextIdx in the above sequence\n        this.runLen = 0 ; // remaining runLength\n        this.currentNum = -1 ; // current Sequence or Number to return as part of next\n    }\n  \n    public int next(int n) {\n       if (n <= runLen){ //case1\n            runLen -= n ;\n            return currentNum ;\n        }\n        if (nextIdx >= A.length) { // case2\n            if (runLen != 0 && n > runLen) {\n                runLen -= n ;\n                currentNum = -1 ;\n            }\n\n            return currentNum ;\n        }\n        while ( n >= runLen && nextIdx < A.length) { // case 3\n            n -= runLen ;\n            runLen = A[nextIdx++] ;\n            currentNum = A[nextIdx++] ;\n        }\n\n        int ret = -1 ;\n        if ( n > 0 ) { //case3 continued\n            runLen -= n ;\n            ret = currentNum ;\n        }\n\n        return ret ;\n    }\n}\n```\n\n\n\t\t\t\n\t\t\t
[]