Solution using Counter and lru_cache
Intuition\n Describe your first thoughts on how to solve this problem. \nMy first thought was, this is a question involving counting, so\nwhy not use Python\'s 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMy first thought was, this is a question involving counting, so\nwhy not use Python\'s nifty ```Counter``` class.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor each query, construct a Counter using the elements in \nsubarray ```arr[left,right+1]```, then take its ```most_common``` element and return it.  I tried this initially and ran out of time\non a large test case.  I then noticed that for this case, the same values for ```left``` and ```right``` were used in many (all?) of the queries.  So, to speed up this case, I wrapped the call to construct a counter from ```arr[left,right+1]``` and take its ```most_common``` element.  Then, I prefixed that function with ```lru_cache( None )```,\nwhich will cache a return the values, bypassing the construction, etc.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity for ```query``` without caching is $$O(n)$$.  With caching, it is somewhat less depending on the amount of repetition in the queries.  \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity varies conversely:   the more repetition of the subarrays, the less the storage, and vice versa.  Worst case, it will vary as the number of queries.\n# Code\n```\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.arr = arr    \n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        element, count =  self.cachedCounter( left, right )\n        if count >= threshold:\n            return element\n        else:\n            return -1\n\n    @lru_cache\n    def cachedCounter( self, left, right ):\n        return Counter( self.arr[ left : right + 1 ] ).most_common( 1 )[ 0 ]      \n\n\n# Your MajorityChecker object will be instantiated and called as such:\n# obj = MajorityChecker(arr)\n# param_1 = obj.query(left,right,threshold)\n```
['Python3']