Python elegant segment-tree solution
\nclass seg_tree:\n    def __init__(self, nums):\n        self.n = len(nums)\n        self.tree = [(0, -1)]*self.n+[(1, n) for n in nums]  # (freq, number)\n   
```\nclass seg_tree:\n    def __init__(self, nums):\n        self.n = len(nums)\n        self.tree = [(0, -1)]*self.n+[(1, n) for n in nums]  # (freq, number)\n        for i in range(self.n-1, 0, -1):\n            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])\n    \n    def merge(self, a, b):\n        _, x = max(a, b)\n        return (a[0]+b[0], x) if a[1]==b[1] else (abs(a[0]-b[0]), x)\n    \n    def st_query(self, l, r):\n        l, r, x = l+self.n, r+self.n, (0, -1)\n        while(l<r):\n            if l%2:\n                x = self.merge(self.tree[l], x)\n                l += 1\n            if r%2:\n                r -= 1\n                x = self.merge(self.tree[r], x)\n            l //= 2\n            r //= 2\n        return x\n\nclass MajorityChecker:\n    \n    def __init__(self, arr):\n        self.seg, self.idx_mp = seg_tree(arr), defaultdict(list)\n        for i in range(len(arr)):\n            self.idx_mp[arr[i]].append(i)\n\t\n    def query(self, l, r, x):\n        n = self.seg.st_query(l, r+1)[1]\n        if n==-1:\n            return -1\n        i = bisect.bisect_left(self.idx_mp[n], l) \n        j = bisect.bisect(self.idx_mp[n], r)\n        return n if j - i >= x else -1    \n```\n\nIf you do not understand this segment-tree implementation\nPlease follow the explanation [HERE](https://codeforces.com/blog/entry/18051)\nOne note is the "query" function refers to the interval **[l, r)**
[]