Python, segment tree, moore voting
\nclass MajorityChecker:\n    def __init__(self, arr: List[int]):\n        self.size = len(arr)\n        self.tree = [None] * self.size * 2\n        self.indexe
```\nclass MajorityChecker:\n    def __init__(self, arr: List[int]):\n        self.size = len(arr)\n        self.tree = [None] * self.size * 2\n        self.indexes = collections.defaultdict(list)\n        self.build(arr)\n        \n    def build(self, arr):\n        for i, n in enumerate(arr):\n            self.tree[i + self.size] = n, 1\n            self.indexes[n].append(i)\n        for i in range(self.size - 1, 0, -1): \n            self.tree[i] = self.merge(self.tree[2 * i], self.tree[2 * i + 1])\n            \n    def merge(self, a, b):\n        ca, cta = a\n        cb, ctb = b\n        if ca == cb:\n            return ca, cta + ctb\n        elif cta >= ctb:\n            return ca, cta - ctb\n        else:\n            return cb, ctb - cta\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        can, ct = self._query(left, right + 1)\n        s = bisect.bisect_left(self.indexes[can], left) \n        e = bisect.bisect(self.indexes[can], right)\n        return can if e - s >= threshold else -1\n    \n    def _query(self, left, right):\n        left += self.size\n        right += self.size\n        ret = 0, 0\n\n        while left < right:\n            if left % 2 == 1:\n                ret = self.merge(ret, self.tree[left])\n                left = left + 1\n            if right % 2 == 1:\n                right = right - 1\n                ret = self.merge(ret ,self.tree[right])\n            left //= 2\n            right //= 2\n        return ret\n```
['Tree', 'Python']