C++ solution, using Map.
freq is {freq : { number: [ index of this number ] } }, for each query, we iterator from freq >= threshold, and used binary search to get the count of a number 
`freq` is {freq : { number: [ index of this number ] } }, for each query, we iterator from freq >= threshold, and used binary search to get the count of a number in range `left` to `right`.\n```\nclass MajorityChecker {\npublic:\n    map<int, unordered_map<int, vector<int> > > freq;\n    MajorityChecker(vector<int>& arr) {\n        unordered_map<int, int> m;\n        for(int n : arr)\n            ++m[n];\n        for(int i = 0; i < arr.size(); ++i){\n            int n = arr[i];\n            freq[m[n]][n].push_back(i);\n        }\n    }\n    \n    int query(int left, int right, int threshold) {\n        int res = -1;\n        auto it = freq.lower_bound(threshold);\n        while(it != freq.end()){\n            for(auto it2 = it->second.begin(); it2 != it->second.end(); ++it2){\n                int num = it2->first;\n                auto &vec = it2->second;\n                if(upper_bound(vec.begin(), vec.end(), right) - lower_bound(vec.begin(), vec.end(), left) >= threshold)\n                    return num;\n            }\n            ++it;\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```
[]