c++ prefix sum -> binary search O(lgn) per query
\nclass RLEIterator {\npublic:\n    RLEIterator(vector<int>& encoding) {\n        long psum = 0;\n        for (int i = 0; i < encoding.size(); i += 2) {\n      
```\nclass RLEIterator {\npublic:\n    RLEIterator(vector<int>& encoding) {\n        long psum = 0;\n        for (int i = 0; i < encoding.size(); i += 2) {\n            val.push_back(encoding[i + 1]);\n            psum += encoding[i];\n            cnt.push_back(psum);\n        }\n        val.push_back(-1);\n    }\n    \n    int next(int n) {\n        n_ += n;\n        auto i = lower_bound(cnt.begin(), cnt.end(), n_) - cnt.begin();\n        return val[i];\n    }\n    vector<long> val, cnt;\n    long n_ = 0;\n};\n```
[]