std::map, O(log(N)
The idea is simple,\nFor every number n, we store the last index of occuring i in a map such that map[i] = n then for every query we just find the lower_bound f
The idea is simple,\nFor every number `n`, we store the last index of occuring `i` in a map such that `map[i] = n` then for every query we just find the `lower_bound` for the index :)\nfor example, let\'s take sample test case :\n`encoding = [3, 8, 0, 9, 2, 5];`\narray =  `8  8  8  5  5`\nindex =` 0  1  2  3  4`\nhence,  map becomes `mp = {{2 : 8}, {4 : 5}}`\n**code : **\n```\nclass RLEIterator {\nprivate:\n    long long idx = -1, sz = 0;\n    map<long long, long long> mp;\npublic:\n    RLEIterator(vector<int>& encoding) {\n        long long cur = -1;\n        for (int i=0; i<encoding.size()-1;i+=2) {\n            if (encoding[i] > 0) {\n                cur += encoding[i];\n                mp[cur] = encoding[i+1];\n                sz = cur+1;\n            }\n        }\n    }\n    \n    int next(int n) {\n        idx += n;\n        if (idx < sz) {\n            auto it = mp.lower_bound(idx);\n            return it->second;\n        } else return -1;\n    }\n};\n```
[]