BEST PYTHON SOLUTION WITH 965MS OF RUNTIME !
\n# Code\n\nclass MajorityChecker:\n  def __init__(self, arr: List[int]):\n    self.arr = arr\n    self.kTimes = 20  # 2^kTimes >> |arr|\n    self.numToIndices 
\n# Code\n```\nclass MajorityChecker:\n  def __init__(self, arr: List[int]):\n    self.arr = arr\n    self.kTimes = 20  # 2^kTimes >> |arr|\n    self.numToIndices = collections.defaultdict(list)\n\n    for i, a in enumerate(self.arr):\n      self.numToIndices[a].append(i)\n\n  def query(self, left: int, right: int, threshold: int) -> int:\n    for _ in range(self.kTimes):\n      randIndex = random.randint(left, right)\n      num = self.arr[randIndex]\n      indices = self.numToIndices[num]\n      l = bisect.bisect_left(indices, left)\n      r = bisect.bisect_right(indices, right)\n      if r - l >= threshold:\n        return num\n\n    return -1\n```
['Python3']