c++ solution
\n# Complexity\n- Time complexity:\n Add your time complexity here, e.g. O(n) \nO( 20 * logn )\n- Space complexity:\n Add your space complexity here, e.g. O(n) 
\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO( 20 * logn )\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass MajorityChecker {\n    unordered_map<int,vector<int>> mp ;\n    vector<int> v ; \n    int trial = 30 ;\npublic:\n    MajorityChecker(vector<int>& arr) {\n        srand(time(NULL));\n        trial = 20 ;\n        int n = arr.size() ;\n        v.clear();\n        mp.clear() ;\n        for(int i = 0 ; i< n ; ++i ){\n            mp[arr[i]].push_back(i) ;\n            v.push_back(arr[i]) ;\n        }\n    }\n    \n    int query(int left, int right, int threshold) {\n        for(int i = 0 ; i< trial ; ++i ){\n            \n            int r_el = v[left + rand()% (right - left + 1 ) ] ;\n            cout<<r_el<<" ";\n            // auto it = mp[r_el].second ; \n            int cnt = upper_bound(mp[r_el].begin() , mp[r_el].end() , right) - upper_bound(mp[r_el].begin() , mp[r_el].end() , left -1 ) ;\n            if( cnt >= threshold ) return r_el ;\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 \n```
['C++']