Python Easy Solution
Code\n\nclass MajorityChecker(object):\n\n    def __init__(self, A):\n        a2i = collections.defaultdict(list)\n        for i, x in enumerate(A):\n          
# Code\n```\nclass MajorityChecker(object):\n\n    def __init__(self, A):\n        a2i = collections.defaultdict(list)\n        for i, x in enumerate(A):\n            a2i[x].append(i)\n        self.A, self.a2i = A, a2i\n\n    def query(self, left, right, threshold):\n        for _ in range(20):\n            a = self.A[random.randint(left, right)]\n            l = bisect.bisect_left(self.a2i[a], left)\n            r = bisect.bisect_right(self.a2i[a], right)\n            if r - l >= threshold:\n                return a\n        return -1\n```
['Python3']