Random Pick
Update: after new test cases were added, other solutions are now TLE. Removed them to avoid confusion.\n\nWe hash-map each unique element to a vector. That vect
> Update: after new test cases were added, other solutions are now TLE. Removed them to avoid confusion.\n\nWe hash-map each unique element to a vector. That vector stores all indexes of that element in the increasing order.\n\n Therefore, we can use a binary search to tell how many times a given element occurs between left and right.\n\n## Random Pick\nWe randomply pick an element from the range, and check the number of its occurances between `l` and `r`.\n\nIf *there is* a majority element, there is more than 50% chance of picking that element.\n\nSo, we can just do a few picks (say, 10) and do the majority check for those picks only.\n\n**C++**\n```cpp\nvector<int> arr;\nunordered_map<int, vector<int>> idx;\nMajorityChecker(vector<int>& arr) : arr(arr) {\n  for (auto i = 0; i < arr.size(); ++i)\n      idx[arr[i]].push_back(i);\n}\nint query(int l, int r, int threshold) {\n  for (auto n = 0; n < 10; ++n) {\n    auto it = idx.find(arr[l + rand() % (r - l + 1)]);\n    const auto &id = it->second;\n    if (upper_bound(begin(id), end(id), r) - \n        lower_bound(begin(id), end(id), l) >= threshold)\n        return it->first;\n  }\n  return -1;\n}\n```
[]