Sweet and simple solution using map and vector
\nclass MajorityChecker {\npublic:\n    unordered_map<int,vector<int>>m;\n    vector<int>v;\n    MajorityChecker(vector<int>& arr) {\n        v=arr;\n        fo
```\nclass MajorityChecker {\npublic:\n    unordered_map<int,vector<int>>m;\n    vector<int>v;\n    MajorityChecker(vector<int>& arr) {\n        v=arr;\n        for(int i=0;i<arr.size();i++){\n            m[arr[i]].push_back(i);\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    int query(int left, int right, int threshold) {\n        for(auto i=0;i<20;i++){\n            int index=rand()%(right-left+1)+left;\n            int val=v[index];\n            \n            int yes=get_occurence(m[val],left,right);\n            if(yes>=threshold)return val;\n        }\n        return -1;\n    }\n};\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * MajorityChecker* obj = new MajorityChecker(arr);\n * int param_1 = obj->query(left,right,threshold);\n */\n```
[]