C++ concise
```\nclass MajorityChecker {\npublic:\n    MajorityChecker(vector& arr) : v(move(arr)) {\n        for(int i=0;i<v.size();i++) indexMap[v[i]].push_back(i);\n    
```\nclass MajorityChecker {\npublic:\n    MajorityChecker(vector<int>& arr) : v(move(arr)) {\n        for(int i=0;i<v.size();i++) indexMap[v[i]].push_back(i);\n    }\n    \n    int query(int left, int right, int threshold) {\n        int len = right-left+1;\n        for(int k=0;k<20;k++){\n            int x = v[left + rand() % len];\n            if(count(left, right, x) >= threshold) return x;\n        }\n        return -1;\n    }\n    \n    int count(int l, int r, int x){\n        const auto& u = indexMap.at(x);\n        auto it1 = lower_bound(u.begin(), u.end(), l);\n        auto it2 = upper_bound(u.begin(), u.end(), r);\n        return it2 - it1;\n    }\n    \n    unordered_map<int, vector<int>> indexMap;\n    vector<int> v;\n};
[]