1157

class MajorityChecker {
public:
    vector<int> a;
    unordered_map<int, vector<int>> idx;
    MajorityChecker(vector<int>& arr) {
        for(auto i = 0; i < arr.size(); ++i)
            idx[arr[i]].push_back(i);
        a = arr;
    }

    int query(int left, int right, int threshold) {
        for(auto n = 0; n < 10; ++n){
            auto num = a[left + rand() % (right - left + 1)];
            if(idx[num].size() < threshold) continue;
            auto up = upper_bound(idx[num].begin(), idx[num].end(), right);
            auto low = lower_bound(idx[num].begin(), idx[num].end(), left);
            if(up-low >= threshold)
                return num;
        }
        return -1;
    }
};

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker* obj = new MajorityChecker(arr);
 * int param_1 = obj->query(left,right,threshold);
 */