Design a data structure that efficiently finds the majority element of a given subarray.
The majority element of a subarray is an element that occurs threshold times or more in the subarray.
Implementing the MajorityChecker class:
MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr .
int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.
1 <= arr.length <= 2 * 10 ^41 <= arr[i] <= 2 * 10 ^40 <= left <= right < arr.lengththreshold <= right - left + 12 * threshold > right - left + 1At most 10 ^4 calls will be made to query .