Simple C++ Solution
\nclass MajorityChecker {\npublic:\n    \n    unordered_map<int, vector<int>> memo;\n    vector<pair<int, int>> vec;\n    \n    static bool comp(pair<int, int> 
```\nclass MajorityChecker {\npublic:\n    \n    unordered_map<int, vector<int>> memo;\n    vector<pair<int, int>> vec;\n    \n    static bool comp(pair<int, int> a, pair<int, int> b) {\n        return (a.first > b.first);\n    }\n    \n    MajorityChecker(vector<int>& arr) {\n  \n        for (int i = 0; i < arr.size(); i++) {\n            memo[arr[i]].push_back(i);\n        }\n        for (unordered_map<int, vector<int>> :: iterator it = memo.begin(); it != memo.end(); it++) {\n            vec.push_back(make_pair(it->second.size(), it->first));\n        }\n        sort(vec.begin(), vec.end(), comp);\n    }\n    \n    int query(int left, int right, int threshold) {\n        \n        if (right - left + 1 < threshold)   return -1;\n        \n        for (int i = 0; i < vec.size(); i++) {\n            int sz = vec[i].first, num = vec[i].second; \n            if (sz < threshold) return -1;\n            vector<int> v = memo[num];\n            vector<int> :: iterator itlow = lower_bound(v.begin(), v.end(), left);\n            if (itlow == v.end())   continue;\n            vector<int> :: iterator itup = lower_bound(v.begin(), v.end(), right);\n            if (itup != v.end() && *itup > right)   --itup;\n            int diff = (itup - itlow);\n            if (itup != v.end())    diff += 1;\n            if (diff >= threshold)  return num;\n        }\n        \n        return -1;\n    }\n};\n\n```
[]