[C++] Binary search
lower_bound(vec.begin(), vec.end(), right + 1) - lower_bound(vec.begin(), vec.end(), left)\ncpp\nclass MajorityChecker {\npublic:\n    unordered_map<int, vector
`lower_bound(vec.begin(), vec.end(), right + 1) - lower_bound(vec.begin(), vec.end(), left)`\n```cpp\nclass MajorityChecker {\npublic:\n    unordered_map<int, vector<int>> mp;\n    vector<int> data;\n    MajorityChecker(vector<int>& arr) {\n        data = arr;\n        for (int i = 0; i < arr.size(); ++i) {\n            mp[arr[i]].push_back(i);\n        }    \n    }\n    \n    int get_occurence(vector<int>& vec, int left, int right) {\n        int nums = lower_bound(vec.begin(), vec.end(), right + 1) - lower_bound(vec.begin(), vec.end(), left);\n        return nums;\n    }\n    \n    int query(int left, int right, int threshold) {\n        // srand((unsigned)time(NULL));\n        for (int i = 0; i < 20; ++i) {\n            int idx = rand() % (right - left + 1) + left;\n            int val = data[idx];\n            int nums = get_occurence(mp[val], left, right);\n            if (nums >= threshold) {\n                return val;\n            } \n        }\n        return -1;\n    }\n    \n};\n```
[]