C++ Apx O( 30 * 2logN) Complexity with binary search
\nclass MajorityChecker {\n    unordered_map<int,vector<int>> inx;\n    vector<int> v;\npublic:\n    MajorityChecker(vector<int>& arr) {\n        v = arr;\n    
```\nclass MajorityChecker {\n    unordered_map<int,vector<int>> inx;\n    vector<int> v;\npublic:\n    MajorityChecker(vector<int>& arr) {\n        v = arr;\n        for(int i=0;i<arr.size();i++){\n            inx[arr[i]].push_back(i);\n        }\n    }\n    \n    int query(int left, int right, int threshold) {\n        srand(time(0));\n        int len = right - left + 1;\n        for(int i=0;i<min(len,30);i++){\n            int randinx = left + rand()%len;    //random index from -> [left .... right]\n            vector<int> &temp = inx[v[randinx]];\n            int c = cnt(temp,right) - cnt(temp,left-1);\n            if(c >= threshold) return v[randinx];\n        }\n        return -1;\n    }\n    //binary search for counting indices less or equal val\n    int cnt(vector<int>& v,int val){\n        int i = -1;\n        for(int j = v.size();j > 0 ;j/=2){\n            while(i+j < v.size() && v[i+j] <= val) i+=j;\n        }\n        return i+1;\n    }\n};\n```
[]