Implementing the class MajorityChecker, which has the following API:

MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
int query(int left, int right, int threshold) has arguments such that:
        
0 <= left <= right < arr.length representing a subarray of arr;
2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray



Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right] that occurs at least threshold times, or -1 if no such element exists.
 
Example:
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

 
Constraints:

1 <= arr.length <= 20000
1 <= arr[i] <= 20000
For each query, 0 <= left <= right < len(arr)
For each query, 2 * threshold > right - left + 1
The number of queries is at most 10000

Difficulty: interview

Starter code:

class MajorityChecker:
    def __init__(self, arr: List[int]):
    def query(self, left: int, right: int, threshold: int) -> int:
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

Solutions:
from collections import defaultdict
from bisect import bisect_left, bisect_right

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.num_idx_dict = defaultdict(list)
        for idx, number in enumerate(arr):
            self.num_idx_dict[number].append(idx)
        self.candidates = sorted(self.num_idx_dict, key=lambda x: len(self.num_idx_dict[x]), reverse=True)
        
    def query(self, left: int, right: int, threshold: int) -> int:
        for number in self.candidates:
            if len(self.num_idx_dict[number]) < threshold:
                return -1
            left_idx = bisect_left(self.num_idx_dict[number], left)
            right_idx = bisect_right(self.num_idx_dict[number], right)
            
            if right_idx - left_idx >= threshold:
                return number
        return -1


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.loc = collections.defaultdict(list)
        for i, n in enumerate(arr):
            self.loc[n].append(i)    
        self.nums = sorted(
            list(self.loc.keys()), 
            key = lambda n: len(self.loc[n]), 
            reverse=True
        )
        print((self.nums))
        
    def query(self, left: int, right: int, threshold: int) -> int:
        # binary search every number in arr
        # find number of num in this range [left, right]
        for n in self.nums:
            if len(self.loc[n]) < threshold: 
                return -1
            l, r = bisect.bisect_left(self.loc[n], left), bisect.bisect_right(self.loc[n], right)
            if r - l >= threshold: 
                return n
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        
        self.idx = collections.defaultdict(list)
        for i,a in enumerate(arr):
            self.idx[a].append(i)
        
        tmp = sorted(list(self.idx.items()), key=lambda x: len(x[1]), reverse=True)
        
        self.order = [x for x,_ in tmp]

    def query(self, left: int, right: int, threshold: int) -> int:
        
        for k in self.order:
            if len(self.idx[k]) < threshold:
                return -1
            l = bisect.bisect_left(self.idx[k], left)
            r = bisect.bisect_right(self.idx[k], right)
            if r-l >= threshold:
                return k
        
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.indices = collections.defaultdict(list)
        for i, n in enumerate(arr):
            self.indices[n].append(i)
        self.nums = sorted(list(self.indices.keys()), key=lambda i: -1*len(self.indices[i]))

    def query(self, left: int, right: int, threshold: int) -> int:
        for n in self.nums:
            if len(self.indices[n]) < threshold: return -1
            l, r = bisect.bisect_left(self.indices[n], left), bisect.bisect_right(self.indices[n], right)
            if r - l >= threshold: return n
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.loc = collections.defaultdict(list)
        for i, n in enumerate(arr):
            self.loc[n].append(i)    
        self.nums = sorted(list(self.loc.keys()), key = lambda n: len(self.loc[n]), reverse=True)
        
    def query(self, left: int, right: int, threshold: int) -> int:
        for n in self.nums:
            if len(self.loc[n]) < threshold: return -1
            l, r = bisect.bisect_left(self.loc[n], left), bisect.bisect_right(self.loc[n], right)
            if r - l >= threshold: return n
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.indices = defaultdict(list)
        for a in set(arr):
            self.indices[a].append(-1)
        for i, a in enumerate(arr):
            self.indices[a].append(i)
        self.A = sorted(list(self.indices.keys()), key=lambda x:-len(self.indices[x]))
        
    def query(self, left: int, right: int, threshold: int) -> int:
        def bs(arr, l, r, target):
            while l<=r:
                m = l+(r-l)//2
                if arr[m]<=target:
                    l = m+1
                else:
                    r = m-1
            return r
        
        for a in self.A:
            lst = self.indices[a]
            if len(lst)<threshold: return -1
            l, r = bs(lst, 0, len(lst)-1, left-1), bs(lst, 0, len(lst)-1, right)
            if r-l>=threshold:
                return a
        
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.loc = collections.defaultdict(list)
        for i, n in enumerate(arr):
            self.loc[n].append(i)    
        self.nums = sorted(list(self.loc.keys()), key = lambda n: len(self.loc[n]), reverse=True)
        
    def query(self, left: int, right: int, threshold: int) -> int:
        for n in self.nums:
            if len(self.loc[n]) < threshold: return -1
            l, r = bisect.bisect_left(self.loc[n], left), bisect.bisect_right(self.loc[n], right)
            if r - l >= threshold: return n
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict

class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.idx = defaultdict(list)
        counts = dict()
        for i, v in enumerate(arr):
            self.idx[v].append(i)
            counts[v] = len(self.idx[v])
        self.counts = list(counts.items())
        self.counts.sort(key=lambda x:x[1], reverse=True)
        

    def query(self, left: int, right: int, threshold: int) -> int:
        for val, count in self.counts:
            if count < threshold:
                break
            indices = self.idx[val]
            start = find_closest(indices, left, lower=False)
            end = find_closest(indices, right, lower=True)
            n_in_range = end - start + 1
            if n_in_range >= threshold:
                return val
        return -1
    
    
    
def find_closest(a: List[int], target: int, lower: bool) -> int:
    low = 0
    high = len(a) - 1
    
    while low <= high:
        m = (low + high) // 2
        if a[m] == target:
            return m
        if a[m] < target:
            low = m + 1
        else:
            high = m - 1
        
    if lower:
        return high
    return low
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


    
from math import log2

class Node:
    def __init__(self,val,freq):
        self.val=val
        self.freq = freq
        
class MajorityChecker:

    def __init__(self, arr: List[int]):
        
        self.arr = arr
        self.locations = {}
        for i,val in enumerate(arr):
            if val in self.locations:
                self.locations[val].append(i)
            else:
                self.locations[val] = [i]
        self.occur = sorted(list(self.locations.items()), reverse=True, key=lambda x: len(x[1]))
    
        print((self.occur))
        
#         self.freq = { i:[] for i in arr }
        
#         self.size = 1 << math.ceil(log2(len(arr))) + 1
        
#         self.st = [0]*self.size
        
#         self.build(0,len(arr)-1,0)
    
        
    
#     def merge(self,a,b):
#         if a.val == b.val:
#             return Node(a.val, a.freq + b.freq)
#         if a.freq>b.freq:
#             return Node(a.val, a.freq-b.freq)
#         return Node(b.val,b.freq-a.freq)
    
#     def pqery(self,l,r,pos,s,e):
#         if s>r or e<l:
#             return Node(0,0)
        
#         if l<=s and r>=e:
#             return self.st[pos]
        
#         mid  = ( s + e )>>1
        
#         a=self.pqery(l,r,2*pos + 1,s,mid)
#         b=self.pqery(l,r,2*pos + 2,mid+1,e)
#         return self.merge(a,b)
        
#     def build(self,start,end,pos):
        
#         if start==end:
#             self.st[pos]=Node(self.arr[start],1)
#             self.freq[self.arr[start]].append(start)
        
#         else:
            
#             mid = (end + start)>>1

#             self.build(start,mid,2*pos + 1)
#             self.build(mid+1,end,2*pos + 2)
#             self.st[pos] = self.merge(self.st[pos*2 + 1],self.st[2*pos + 2])
            
            
    def lower_bound(self,arr,x):
        l=0
        r=len(arr)-1
        while l<=r:
            mid = (l+r )>> 1
            if arr[mid]<x:
                l=mid+1
            else:
                r=mid-1
        return l
            
            
    def upper_bound(self,arr,x):
        l=0
        r=len(arr)-1
        while l<=r:
            mid = (l+r) >> 1
            if arr[mid]<=x:
                l=mid+1
            else:
                r=mid-1
        return r+1
            
        
    def query(self, left: int, right: int, threshold: int) -> int:
        for i,j in self.occur:
            if len(j)<threshold:
                return -1
            s = self.lower_bound(j,left)
            e = self.upper_bound(j,right)
            if e-s>=threshold:
                return i
            
        return -1
#         candidate = self.pqery(left,right,0,0,(len(self.arr)-1))
#         # print(self.freq,candidate.val)
#         if candidate.val==0:return -1
        
#         s = self.lower_bound(self.freq[candidate.val],left)
#         e= self.upper_bound(self.freq[candidate.val],right)
#         # print(e,s)
#         if (e-s) >=threshold :
#             return candidate.val
#         else:
#             return -1


        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = []
        hsh = {}
        from sortedcontainers import SortedList
        
        
        for i in range(len(arr)):
            if arr[i] not in hsh:
                hsh[arr[i]] = len(self.arr)
                self.arr.append([arr[i], SortedList()])
            self.arr[hsh[arr[i]]][1].add(i)
            
        self.arr.sort(key = lambda x: len(x[1]), reverse=True)

    def query(self, left: int, right: int, threshold: int) -> int:
        
        for i in self.arr:
            if len(i[1]) < threshold:
                return -1
            
            l = i[1].bisect_left(left)
            r = i[1].bisect_right(right)
            
            if r - l >= threshold:
                return i[0]
            
        return -1

        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict
from bisect import bisect_left, bisect_right

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.el_to_idx = defaultdict(list)
        
        for i, val in enumerate(arr):
            self.el_to_idx[val].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        N = 10
        for _ in range(N):
            val = self.arr[random.randint(left, right)]
            indices = self.el_to_idx[val]
            lo = bisect_left(indices, left)
            hi = bisect_right(indices, right)

            if hi - lo >= threshold:
                return val
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict
from bisect import bisect_left, bisect_right

class MajorityChecker:
    def __init__(self, arr):
        
        # key   : number
        # value : list of indices for number
        self.num_idx_dict = defaultdict( list )
        
        # Append index to corresoinding number's dictionary
        for idx, number in enumerate( arr ):
            
            self.num_idx_dict[ number ].append( idx )
        
        # With descending order of number of occurrences
        self.candidates = sorted( self.num_idx_dict, key = lambda x: len(self.num_idx_dict[x]), reverse = True)

        
    def query(self, left, right, threshold):
        
        for number in self.candidates:
            
            # Longest occurrences is smaller than threhsold, then no solution
            if len( self.num_idx_dict[number] ) < threshold:
                return -1
            
            left_idx = bisect_left( self.num_idx_dict[number], left)
            right_idx = bisect_right( self.num_idx_dict[number], right)
            
            if right_idx - left_idx >= threshold:
                return number
            
        return -1


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.idxes = collections.defaultdict(list)
        for (i, n) in enumerate(arr):
            self.idxes[n].append(i)
        self.arr = arr

    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(10):
            n = self.arr[random.randint(left, right)]
            l = bisect.bisect_left(self.idxes[n], left)
            r = bisect.bisect_right(self.idxes[n], right)
            if r - l >= threshold:
                return n
        return -1
    
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict

class MajorityChecker(object):

    def __init__(self, A):
        B = defaultdict(list)
        for idx, a in enumerate(A):
            B[a].append(idx)
        self.A, self.B = A, B

    def query(self, left, right, threshold):
        ss = set()
        for _ in range(10):
            idx = random.randint(left, right)
            if idx in ss:
                continue
            else: 
                ss.add(idx)
                a = self.A[idx]
                l = bisect.bisect_left(self.B[a], left)
                r = bisect.bisect_right(self.B[a], right)
                if r - l >= threshold:
                    return a
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker(object):

    def __init__(self, A):
        a2i = collections.defaultdict(list)
        for i, x in enumerate(A):
            a2i[x].append(i)
        self.A, self.a2i = A, a2i

    def query(self, left, right, threshold):
        ss = set()
        for _ in range(20):
            a = self.A[random.randint(left, right)]
            if a in ss:
                continue
            else:
                ss.add(a)
                l = bisect.bisect_left(self.a2i[a], left)
                r = bisect.bisect_right(self.a2i[a], right)
                if r - l >= threshold:
                    return a
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict
from bisect import bisect_left, bisect_right

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.el_to_idx = defaultdict(list)
        
        for i, val in enumerate(arr):
            self.el_to_idx[val].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        N = 15
        for _ in range(15):
            val = self.arr[random.randint(left, right)]
            indices = self.el_to_idx[val]
            lo = bisect_left(indices, left)
            hi = bisect_right(indices, right)

            if hi - lo >= threshold:
                return val
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.x_idxs = x_idxs = defaultdict(list)
        for i, x in enumerate(arr):
            x_idxs[x].append(i)
        self.a = arr
        self.n = n = len(arr)
        self.tree = [-1] * (n * 4)
        self.build_tree(1, 0, n - 1)

    def build_tree(self, v, l, r):
        a, tree = self.a, self.tree
        if l == r:
            tree[v] = a[l]
            return
        mid = (l + r) // 2
        self.build_tree(2 * v, l, mid)
        self.build_tree(2 * v + 1, mid + 1, r)
        if tree[2 * v] != -1 and self.count(tree[2 * v], l, r) * 2 > r - l + 1:
            tree[v] = tree[2 * v]
        elif tree[2 * v + 1] != -1 and self.count(tree[2 * v + 1], l, r) * 2 > r - l + 1:
            tree[v] = tree[2 * v + 1]

    def count(self, x, l, r):
        f = bisect.bisect_right
        idxs = self.x_idxs[x]
        return f(idxs, r) - f(idxs, l - 1)

    def query_tree(self, v, l, r, queryl, queryr):
        tree = self.tree
        if queryr < l or r < queryl:
            return -1, -1
        if queryl <= l and r <= queryr:
            if tree[v] == -1:
                return -1, -1
            x = tree[v]
            xcount = self.count(x, queryl, queryr)
            return (x, xcount) if xcount * 2 > queryr - queryl + 1 else (-1, -1)
        mid = (l + r) // 2
        res_left = self.query_tree(2 * v, l, mid, queryl, queryr)
        if res_left[0] > -1:
            return res_left
        res_right = self.query_tree(2 * v + 1, mid + 1, r, queryl, queryr)
        if res_right[0] > -1:
            return res_right
        return -1, -1

    def query(self, left, right, threshold):
        res = self.query_tree(1, 0, self.n - 1, left, right)
        if res[1] >= threshold:
            return res[0]
        return -1
    

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.loc = collections.defaultdict(list)
        for i, n in enumerate(arr):
            self.loc[n].append(i)    
        self.nums = sorted(list(self.loc.keys()), key = lambda n: len(self.loc[n]), reverse=True)
        
    def query(self, left: int, right: int, threshold: int) -> int:
        for n in self.nums:
            if len(self.loc[n]) < threshold: return -1
            l, r = bisect.bisect_left(self.loc[n], left), bisect.bisect_right(self.loc[n], right)
            if r - l >= threshold: return n
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        a2i = collections.defaultdict(list)
        for i,a in enumerate(arr):
            a2i[a].append(i)
        
        self.a2i = a2i
        

    def query(self, left: int, right: int, threshold: int) -> int:
        
        for _ in range(15):
            a = self.arr[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.pos = collections.defaultdict(list) 
        for k, v in enumerate(arr):
            self.pos[v].append(k)
        self.runtime = 20
        self.a = arr

    def query(self, left: int, right: int, threshold: int) -> int:
    
        for i in range(self.runtime):
           # //calculate the frequence of a randomly picked value in the given range
            val = self.a[random.randint(left, right)]
            ll = bisect.bisect_left(self.pos[val], left)
            rr = bisect.bisect_right(self.pos[val], right)
            if (rr-ll) >= threshold:
                return val
        return -1
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker(object):

    def __init__(self, A):
        a2i = collections.defaultdict(list)
        for i, x in enumerate(A):
            a2i[x].append(i)
        self.A, self.a2i = A, a2i

    def query(self, left, right, threshold):
        for _ in range(20):
            a = self.A[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.x_idxs = x_idxs = defaultdict(list)
        for i, x in enumerate(arr):
            x_idxs[x].append(i)
        self.xs = sorted(list(x_idxs.keys()), key=lambda x: -len(x_idxs[x]))

    def query(self, left: int, right: int, threshold: int) -> int:
        for x in self.xs:
            idxs = self.x_idxs[x]
            if len(idxs) < threshold:
                break
            r = bisect.bisect_right(idxs, right)
            l = bisect.bisect_right(idxs, left - 1)
            if r - l >= threshold:
                return x
        return -1
    

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        a2i = collections.defaultdict(list)
        for i,a in enumerate(arr):
            a2i[a].append(i)
        
        self.a2i = a2i
        

    def query(self, left: int, right: int, threshold: int) -> int:
        
        for _ in range(16):
            a = self.arr[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.A = arr
        self.itemIdx = collections.defaultdict(list)
        for i, x in enumerate(self.A):
            self.itemIdx[x].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(20):
            x = self.A[random.randint(left, right)]
            l = bisect.bisect_left(self.itemIdx[x], left)
            r = bisect.bisect_right(self.itemIdx[x], right)
            if r-l >= threshold:
                return x
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.N = len(arr)
        self.max_len = 1 << ceil(log2(self.N))+1
        self.seg = [None]*self.max_len
        self.build(1, 0, self.N-1, arr)
        self.indices = defaultdict(list)
        for i, a in enumerate(arr):
            self.indices[a].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        def bs(arr, l, r, target):
            while l<=r:
                m = l+(r-l)//2
                if arr[m]<=target:
                    l = m+1
                else:
                    r = m-1
            return r
        
        major = self.seg_query(1, 0, self.N-1, left, right)[0]
        lst = self.indices[major]
        l, r = bs(lst, 0, len(lst)-1, left-1), bs(lst, 0, len(lst)-1, right)
        if r-l>=threshold:
            return major
        return -1
        
    def build(self, idx, s, e, arr):
        if s==e:
            self.seg[idx] = [arr[s], 1]
            return
        
        m = s+(e-s)//2
        self.build(2*idx, s, m, arr)
        self.build(2*idx+1, m+1, e, arr)
        self.seg[idx] = self.merge(self.seg[2*idx], self.seg[2*idx+1])
        
    def seg_query(self, idx, s, e, l, r):
        if s>=l and e<=r:
            return self.seg[idx]
        if s>r or e<l:
            return [0, 0]
        m = s+(e-s)//2
        return self.merge(self.seg_query(2*idx, s, m, l, r), self.seg_query(2*idx+1, m+1, e, l, r))
    
    def merge(self, A, B):
        lv, lf = A
        rv, rf = B
        if lv==rv:
            return [lv, lf+rf]
        else:
            if lf>rf:
                return [lv, lf-rf]
            else:
                return [rv, rf-lf]
            
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:
    import bisect
    import random
    def __init__(self, arr: List[int]):
        self.pos = collections.defaultdict(list)
        for k, v in enumerate(arr):
            self.pos[v].append(k)
        self.runtime = 20
        self.a = arr
            
            
        
        

    def query(self, left: int, right: int, threshold: int) -> int:
        for i in range(self.runtime):
            val = self.a[random.randint(left, right)]
            ll = bisect.bisect_left(self.pos[val], left)
            rr = bisect.bisect_right(self.pos[val], right)
            if (rr-ll) >= threshold:
                return val
        return -1
                
            
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.N = len(arr)
        self.max_len = 1 << ceil(log2(self.N))+1
        self.seg = [None]*self.max_len
        self.seg_build(1, 0, self.N-1, arr)
        self.indices = defaultdict(list)
        for i, a in enumerate(arr):
            self.indices[a].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        def bs(arr, l, r, target):
            while l<=r:
                m = l+(r-l)//2
                if arr[m]<=target:
                    l = m+1
                else:
                    r = m-1
            return r
        
        major = self.seg_query(1, 0, self.N-1, left, right)[0]
        lst = self.indices[major]
        l, r = bs(lst, 0, len(lst)-1, left-1), bs(lst, 0, len(lst)-1, right)
        if r-l>=threshold:
            return major
        return -1
    
    def seg_build(self, idx, s, e, arr):
        if s==e:
            self.seg[idx] = [arr[s], 1]
            return
        
        mid = s+(e-s)//2
        self.seg_build(2*idx, s, mid, arr)
        self.seg_build(2*idx+1, mid+1, e, arr)
        self.seg[idx] = self.merge(self.seg[2*idx], self.seg[2*idx+1])
        
    def seg_query(self, idx, s, e, l, r):
        if s>=l and e<=r:
            return self.seg[idx]
        
        if s>r or e<l:
            return [0, 0]
        
        mid = s+(e-s)//2
        return self.merge(self.seg_query(2*idx, s, mid, l, r), self.seg_query(2*idx+1, mid+1, e, l, r))
    
    def merge(self, A, B):
        lv, lf = A
        rv, rf = B
        if lv==rv:
            return [lv, lf+rf]
        else:
            if lf>rf:
                return [lv, lf-rf]
            else:
                return [rv, rf-lf]
    
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        a2i = collections.defaultdict(list)
        for i,a in enumerate(arr):
            a2i[a].append(i)
        
        self.a2i = a2i
        

    def query(self, left: int, right: int, threshold: int) -> int:
        
        for _ in range(20):
            a = self.arr[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker(object):

    def __init__(self, A):
        a2i = collections.defaultdict(list)
        for i, x in enumerate(A):
            a2i[x].append(i)
        self.A, self.a2i = A, a2i

    def query(self, left, right, threshold):
        for _ in range(20):
            a = self.A[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        d = collections.defaultdict(list)
        for j, x in enumerate(arr):
            d[x].append(j)
        self.arr, self.d = arr, d

    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(20):
            a = self.arr[random.randint(left, right)]
            l = bisect.bisect_left(self.d[a], left)
            r = bisect.bisect_right(self.d[a], right)
            if r - l >= threshold:
                return a
        return -1




# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.memo = collections.defaultdict(list)
        for i, x in enumerate(arr):
            self.memo[x].append(i)
        self.arr = arr

    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(20):    
            r = self.arr[random.randint(left, right)]
            lo = bisect.bisect_left(self.memo[r], left)
            hi = bisect.bisect_right(self.memo[r], right)
            if hi - lo >= threshold:
                return r
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict
import bisect
class MajorityChecker:
    #Use a dictionary to store the index of each element in arr and sort the dictionary by the frequence of each value in arr
    #Use bisection search to fix the insertion position of left and right, and compare right-left to the threshold 

    def __init__(self, arr: List[int]):
        self.d = defaultdict(list)
        for i, value in enumerate(arr):
            self.d[value].append(i)
            
        self.d = sorted(list(self.d.items()), key = lambda x: -len(x[1]))
        

    def query(self, left: int, right: int, threshold: int) -> int:
        for num, idxs in self.d:
            if len(idxs) >= threshold:
                low = bisect.bisect_left(idxs, left)
                high = bisect.bisect_right(idxs, right)
                if (high - low) >= threshold:
                    return num
            else: break
        return -1
        
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker(object):

    def __init__(self, A):
        a2i = collections.defaultdict(list)
        for i, x in enumerate(A):
            a2i[x].append(i)
        self.A, self.a2i = A, a2i

    def query(self, left, right, threshold):
        ss = set()
        for _ in range(30):
            a = self.A[random.randint(left, right)]
            if a in ss:
                continue
            else:
                ss.add(a)
                l = bisect.bisect_left(self.a2i[a], left)
                r = bisect.bisect_right(self.a2i[a], right)
                if r - l >= threshold:
                    return a
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict

class MajorityChecker(object):

    def __init__(self, A):
        B = defaultdict(list)
        for idx, a in enumerate(A):
            B[a].append(idx)
        self.A, self.B = A, B

    def query(self, left, right, threshold):
        ss = set()
        for _ in range(20):
            idx = random.randint(left, right)
            if idx in ss:
                continue
            else: 
                ss.add(idx)
                a = self.A[idx]
                l = bisect.bisect_left(self.B[a], left)
                r = bisect.bisect_right(self.B[a], right)
                if r - l >= threshold:
                    return a
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class Node:
    def __init__(self,left,right):
        self.i = left
        self.j = right
        self.left = None
        self.right = None
        self.Maj = None
        self.Maj_f = 0
        
class MajorityChecker:
    def __init__(self, arr: List[int]):
        def DFS(i,j):
            node = Node(i,j)
            if i == j :
                node.Maj = arr[i]
                node.Maj_f = 1
            else:
                m = (i+j)//2
                node.left,a,b = DFS(i,m)
                node.right,c,d = DFS(m+1,j)
                if a == c:
                    node.Maj = a 
                    node.Maj_f = b+d
                elif b > d:
                    node.Maj = a 
                    node.Maj_f = b-d
                else:
                    node.Maj = c
                    node.Maj_f = d-b
            return node,node.Maj,node.Maj_f 
        
        self.root = DFS(0,len(arr)-1)[0]
        self.index = defaultdict(list)
        for i,num in enumerate(arr):
            self.index[num].append(i)
    
    def DFS(self,node,l,r):
        if node.i == l and node.j == r:
            return node.Maj,node.Maj_f
        m = (node.i+node.j)//2
        if l > m :
            return self.DFS(node.right,l,r)
        elif r < m+1:
            return self.DFS(node.left,l,r)
        else:
            a,b = self.DFS(node.left,l,m)
            c,d = self.DFS(node.right,m+1,r)
            if a == c :
                return a,b+d
            elif b > d :
                return a,b-d
            else:
                return c,d-b

    def query(self, left: int, right: int, threshold: int) -> int:
        
        candidate = self.DFS(self.root,left,right)[0]
        if threshold <= bisect.bisect_right(self.index[candidate],right) - bisect.bisect_left(self.index[candidate],left):
            return candidate
        else:
            return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class Node:
    def __init__(self,left,right):
        self.left = left
        self.right = right
        self.left_child = None
        self.right_child = None
        self.Maj_num = None
        self.Maj_f = 0
        
class MajorityChecker:
    def __init__(self, arr: List[int]):
        def create_Tree(i,j):
            cur = Node(i,j)
            if i == j:
                cur.Maj_num = arr[i]
                cur.Maj_f = 1
            else:
                m = (i+j)//2
                cur.left_child , n1 , f1 = create_Tree(i,m)
                cur.right_child , n2 ,f2 = create_Tree(m+1,j)
                if n1 == n2:
                    cur.Maj_num = n1
                    cur.Maj_f = f1+f2
                else:
                    if f1 >= f2:
                        cur.Maj_num = n1
                        cur.Maj_f = f1-f2
                    else:
                        cur.Maj_num = n2
                        cur.Maj_f = f2-f1
            return cur,cur.Maj_num,cur.Maj_f
        
        self.root = create_Tree(0,len(arr)-1)[0]
        self.index = defaultdict(list)
        for i,num in enumerate(arr):
            self.index[num].append(i)
            
    def traverse(self,node,i,j):
        if i == node.left and j == node.right:
            return node.Maj_num, node.Maj_f
        m = (node.left + node.right)//2
        
        if i > m :
            return self.traverse(node.right_child,i,j)
        if j <= m:
            return self.traverse(node.left_child,i,j)
        else:
            n1,f1 = self.traverse(node.left_child,i,m)
            n2,f2 = self.traverse(node.right_child,m+1,j)
            if n1 == n2:
                return n1,f1+f2
            else:
                if f1 >= f2:
                    return n1,f1-f2
                else:
                    return n2,f2-f1             
    def query(self, left: int, right: int, threshold: int) -> int:
        candidate = self.traverse(self.root,left,right)[0]
        if threshold <= bisect.bisect_right(self.index[candidate],right) - bisect.bisect_left(self.index[candidate],left):
            return candidate
        else:
            return -1
        


from bisect import bisect, bisect_left
class Node():
    def __init__(self, val, freq):
        self.val = val
        self.freq = freq
        
def merge(a,b):
    if a.val == b.val:
        return Node(a.val, a.freq+b.freq)
    if a.freq > b.freq:
        return Node(a.val, a.freq - b.freq)
    return Node(b.val, b.freq - a.freq)

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.arr = arr
        self.size = 1 << math.ceil(math.log(self.n, 2)) + 1 
        self.tree = [None] * self.size 
        self.indexes = {i: [] for i in self.arr}
        self.build(0, 0, self.n-1)
           
    def build(self, pos, l, r):
        if l == r:
            self.tree[pos] = Node(self.arr[l], 1) 
            self.indexes[self.arr[l]].append(l)
        else:
            mid = l + r >> 1
            self.build(pos*2+1, l, mid) 
            self.build(pos*2+2,mid+1, r) 
            self.tree[pos] = merge(self.tree[pos*2+1], self.tree[pos*2+2]) 
        
    def pquery(self, pos, start, end, l ,r):
        if l > end or r < start:
            return Node(0, 0)
        if start <= l and r <= end:
            return self.tree[pos] 
        mid = l + r >> 1
        a = self.pquery(pos*2+1, start, end, l, mid) 
        b = self.pquery(pos*2+2, start, end, mid+1, r) 
        return merge(a,b)

    def query(self, l: int, r: int, threshold: int) -> int:
        candidate = self.pquery(0, l, r, 0 , self.n-1).val
        if candidate == 0 : return -1
        s = bisect_left(self.indexes[candidate], l) 
        e = bisect(self.indexes[candidate], r)
        return candidate if e - s >= threshold else -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class Node:
    def __init__(self,left,right):
        self.i = left
        self.j = right
        self.left = None
        self.right = None
        self.Maj = None
        self.Maj_f = 0
        
class MajorityChecker:
    def __init__(self, arr: List[int]):
        def DFS(i,j):
            node = Node(i,j)
            if i == j :
                node.Maj = arr[i]
                node.Maj_f = 1
            else:
                m = (i+j)//2
                node.left,a,b = DFS(i,m)
                node.right,c,d = DFS(m+1,j)
                if a == c:
                    node.Maj = a 
                    node.Maj_f = b+d
                elif b > d:
                    node.Maj = a 
                    node.Maj_f = b-d
                else:
                    node.Maj = c
                    node.Maj_f = d-b
            return node,node.Maj,node.Maj_f 
        
        self.root = DFS(0,len(arr)-1)[0]
        self.index = defaultdict(list)
        for i,num in enumerate(arr):
            self.index[num].append(i)
    
    def DFS(self,node,l,r):
        if node.i == l and node.j == r:
            return node.Maj,node.Maj_f
        m = (node.i+node.j)//2
        if l > m :
            return self.DFS(node.right,l,r)
        elif r < m+1:
            return self.DFS(node.left,l,r)
        else:
            a,b = self.DFS(node.left,l,m)
            c,d = self.DFS(node.right,m+1,r)
            if a == c :
                return a,b+d
            elif b > d :
                return a,b-d
            else:
                return c,d-b

    def query(self, left: int, right: int, threshold: int) -> int:
        
        candidate = self.DFS(self.root,left,right)[0]
        if threshold <= bisect.bisect_right(self.index[candidate],right) - bisect.bisect_left(self.index[candidate],left):
            return candidate
        else:
            return -1

class MajorityChecker:
    # copied https://leetcode.com/problems/online-majority-element-in-subarray/discuss/355848/Python-Binary-Search-%2B-Find-the-Majority-Element

    def __init__(self, arr: List[int]):
        a2i = collections.defaultdict(list)
        for i, x in enumerate(arr):
            a2i[x].append(i)
        self.A, self.a2i = arr, a2i

    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(20): # 用的是概率，20次都没有找到这个数的概率太小 -> 0.49^20 
            a = self.A[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:
    # copied https://leetcode.com/problems/online-majority-element-in-subarray/discuss/355848/Python-Binary-Search-%2B-Find-the-Majority-Element

    def __init__(self, arr: List[int]):
        a2i = collections.defaultdict(list)
        for i, x in enumerate(arr):
            a2i[x].append(i)
        self.A, self.a2i = arr, a2i

    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(20):
            a = self.A[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict

import bisect

class MajorityChecker:

  def __init__(self, arr: List[int]):
    # d: value -> indices
    self.d = defaultdict(list)
    # Q0458, index each value by binary, in or not in 15 groups, 2^5 = 32768 > 20000.
    self.q = [[0] * 15 for _ in range(len(arr) + 1)]
    for i, x in enumerate(arr):
      self.d[x].append(i)
      for j in range(15):
        self.q[i + 1][j] = self.q[i][j] + (x & 1)
        x >>= 1
    
  def query(self, left: int, right: int, threshold: int) -> int:
    # candidate
    x = 0
    for j in range(15):
      if self.q[right + 1][j] - self.q[left][j] >= threshold:
        x |= 1 << j
    return x if bisect.bisect_right(self.d[x], right) - bisect.bisect_left(self.d[x], left) >= threshold else -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.x_idxs = x_idxs = defaultdict(list)
        for i, x in enumerate(arr):
            x_idxs[x].append(i)
        self.xs = sorted((len(idxs), x) for x, idxs in list(x_idxs.items()))[::-1]

    def query(self, left: int, right: int, threshold: int) -> int:
        for length, x in self.xs:
            if length < threshold:
                break
            idxs = self.x_idxs[x]
            r = bisect.bisect_right(idxs, right)
            l = bisect.bisect_right(idxs, left - 1)
            if r - l >= threshold:
                return x
        return -1

    

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, A):
        a2i = collections.defaultdict(list)
        for i, x in enumerate(A):
            a2i[x].append(i)
        self.A, self.a2i = A, a2i

    def query(self, left, right, threshold):
        for _ in range(20):
            a = self.A[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:
    def __init__(self, nums):
        atoi = defaultdict(list)
        for i, num in enumerate(nums):
            atoi[num].append(i)
        self.nums = nums
        self.atoi = atoi

    def query(self, left, right, threshold):
        for _ in range(20):
            rand = self.nums[random.randint(left, right)]
            left_element = bisect.bisect_left(self.atoi[rand], left)
            right_element = bisect.bisect(self.atoi[rand], right) 
            if right_element - left_element >= threshold:
                return rand
        return -1

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        a2i = collections.defaultdict(list)
        for i,a in enumerate(arr):
            a2i[a].append(i)
        
        self.a2i = a2i
        

    def query(self, left: int, right: int, threshold: int) -> int:
        
        for _ in range(40):
            a = self.arr[random.randint(left, right)]
            l = bisect.bisect_left(self.a2i[a], left)
            r = bisect.bisect_right(self.a2i[a], right)
            if r - l >= threshold:
                return a
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class Node:
    def __init__(self,left,right):
        self.i = left
        self.j = right
        self.left = None
        self.right = None
        self.Maj = None
        self.Maj_f = 0
        
class MajorityChecker:
    def __init__(self, arr: List[int]):
        def DFS(i,j):
            node = Node(i,j)
            if i == j :
                node.Maj = arr[i]
                node.Maj_f = 1
            else:
                m = (i+j)//2
                node.left,a,b = DFS(i,m)
                node.right,c,d = DFS(m+1,j)
                if a == c:
                    node.Maj = a 
                    node.Maj_f = b+d
                elif b > d:
                    node.Maj = a 
                    node.Maj_f = b-d
                else:
                    node.Maj = c
                    node.Maj_f = d-b
            return node,node.Maj,node.Maj_f 
        
        self.root = DFS(0,len(arr)-1)[0]
        self.index = defaultdict(list)
        for i,num in enumerate(arr):
            self.index[num].append(i)
    
    def DFS(self,node,l,r):
        if node.i == l and node.j == r:
            return node.Maj,node.Maj_f
        m = (node.i+node.j)//2
        if l > m :
            return self.DFS(node.right,l,r)
        elif r < m+1:
            return self.DFS(node.left,l,r)
        else:
            a,b = self.DFS(node.left,l,m)
            c,d = self.DFS(node.right,m+1,r)
            if a == c :
                return a,b+d
            elif b > d :
                return a,b-d
            else:
                return c,d-b

    def query(self, left: int, right: int, threshold: int) -> int:
        
        candidate = self.DFS(self.root,left,right)[0]
        print(candidate)
        if threshold <= bisect.bisect_right(self.index[candidate],right) - bisect.bisect_left(self.index[candidate],left):
            return candidate
        else:
            return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict

class MajorityChecker(object):

    def __init__(self, A):
        B = defaultdict(list)
        for idx, a in enumerate(A):
            B[a].append(idx)
        self.A, self.B = A, B

    def query(self, left, right, threshold):
        ss = set()
        for _ in range(40):
            idx = random.randint(left, right)
            if idx in ss:
                continue
            else: 
                ss.add(idx)
                a = self.A[idx]
                l = bisect.bisect_left(self.B[a], left)
                r = bisect.bisect_right(self.B[a], right)
                if r - l >= threshold:
                    return a
        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


import numpy as np
class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = np.array(arr)



    def query(self, left: int, right: int, threshold: int) -> int:
        
        

        count = np.bincount(self.arr[left:right+1])
        x = np.argmax(count)
        if count[x] >= threshold:
            return x


        return -1
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.data = defaultdict(list)
        for i,num in enumerate(arr):
            self.data[num] += [i]

    def query(self, left: int, right: int, threshold: int) -> int:
        counter = defaultdict(int)
        for _ in range(32):
            index = random.randint(left, right)
            counter[self.arr[index]] += 1
        max_cnts = sorted([(value,key) for key,value in list(counter.items())], reverse=True)[:2]
        
        for value,key in max_cnts:
            i = bisect.bisect_left(self.data[key],  left)
            j = bisect.bisect_right(self.data[key], right)
            if j - i >= threshold:
                return key
        return -1
        
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


    
from math import log2

class Node:
    def __init__(self,val,freq):
        self.val=val
        self.freq = freq
        
class MajorityChecker:

    def __init__(self, arr: List[int]):
        
        self.arr = arr
        
        self.freq = { i:[] for i in arr }
        
        self.size = 1 << math.ceil(log2(len(arr))) + 1
        
        self.st = [0]*self.size
        
        self.build(0,len(arr)-1,0)
    
    
    def merge(self,a,b):
        if a.val == b.val:
            return Node(a.val, a.freq + b.freq)
        if a.freq>b.freq:
            return Node(a.val, a.freq-b.freq)
        return Node(b.val,b.freq-a.freq)
    
    def pqery(self,l,r,pos,s,e):
        if s>r or e<l:
            return Node(0,0)
        
        if l<=s and r>=e:
            return self.st[pos]
        
        mid  = ( s + e )>>1
        
        a=self.pqery(l,r,2*pos + 1,s,mid)
        b=self.pqery(l,r,2*pos + 2,mid+1,e)
        return self.merge(a,b)
        
    def build(self,start,end,pos):
        
        if start==end:
            self.st[pos]=Node(self.arr[start],1)
            self.freq[self.arr[start]].append(start)
        
        else:
            
            mid = (end + start)>>1

            self.build(start,mid,2*pos + 1)
            self.build(mid+1,end,2*pos + 2)
            self.st[pos] = self.merge(self.st[pos*2 + 1],self.st[2*pos + 2])
            
            
    def lower_bound(self,arr,x):
        l=0
        r=len(arr)-1
        while l<=r:
            mid = (l+r )>> 1
            if arr[mid]<x:
                l=mid+1
            else:
                r=mid-1
        return l
            
            
    def upper_bound(self,arr,x):
        l=0
        r=len(arr)-1
        while l<=r:
            mid = (l+r) >> 1
            if arr[mid]<=x:
                l=mid+1
            else:
                r=mid-1
        return r+1
            
        
    def query(self, left: int, right: int, threshold: int) -> int:
        
        candidate = self.pqery(left,right,0,0,(len(self.arr)-1))
        # print(self.freq,candidate.val)
        if candidate.val==0:return -1
        
        s = self.lower_bound(self.freq[candidate.val],left)
        e= self.upper_bound(self.freq[candidate.val],right)
        # print(e,s)
        if (e-s) >=threshold :
            return candidate.val
        else:
            return -1

        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.idxes = collections.defaultdict(list)
        for (i, n) in enumerate(arr):
            self.idxes[n].append(i)
        self.arr = arr
        self.st = SegmentTree(len(arr), arr, self.idxes)

    def query(self, left: int, right: int, threshold: int) -> int:
        maj = self.st.query_maj(left, right)
        if maj:
            l, r = bisect.bisect_left(self.idxes[maj], left), bisect.bisect(self.idxes[maj], right)
            if r - l >= threshold:
                return maj
        return -1

class SegmentTree:
    
    def __init__(self, n, arr, idxes):
        self.root = Node(0, n - 1, arr, idxes)
        
    def query_maj(self, lo, hi):
        return self.root.query_maj(lo, hi)

class Node:
    
    def __init__(self, lo, hi, arr, idxes):
        self.lo, self.hi = lo, hi
        self.lc, self.rc = None, None
        self.arr, self.idxes = arr, idxes
        self.maj = None
        
    def query_maj(self, lo, hi):
        
        def is_maj(n):
            if not n:
                return False
            
            l = bisect.bisect_left(self.idxes[n], lo)
            r = bisect.bisect(self.idxes[n], hi)
            return (r - l << 1) > hi - lo
        
        if lo > hi or self.lo > hi or self.hi < lo:
            return None
        
        if lo <= self.lo <= self.hi <= hi:
            if not self.maj:
                if self.lo == self.hi:
                    self.maj = self.arr[self.lo]
                else:
                    l, r = None, None
                    mi = (self.lo + self.hi) >> 1
                    if not self.lc:
                        self.lc = Node(self.lo, mi, self.arr, self.idxes)
                    l = self.lc.query_maj(self.lo, mi)
                    if not self.rc:
                        self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
                    r = self.rc.query_maj(mi + 1, self.hi)
                        
                    self.maj = l if is_maj(l) else r if is_maj(r) else -1
            return self.maj
        
        mi = (self.lo + self.hi) >> 1
        l, r = None, None
        if lo <= mi:
            if not self.lc:
                self.lc = Node(self.lo, mi, self.arr, self.idxes)
            l = self.lc.query_maj(max(self.lo, lo), min(mi, hi))
        if mi + 1 <= hi:
            if not self.rc:
                self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
            r = self.rc.query_maj(max(lo, mi + 1), min(self.hi, hi))
        return l if is_maj(l) else r if is_maj(r) else -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.x_idxs = x_idxs = defaultdict(list)

        for i, x in enumerate(arr):
            x_idxs[x].append(i)

        self.xs = sorted(list(x_idxs.keys()), key=lambda x: -len(x_idxs[x]))

    def query(self, left: int, right: int, threshold: int) -> int:
        br = bisect.bisect_right
        for x in self.xs:
            idxs = self.x_idxs[x]
            if len(idxs) < threshold:
                break
            if br(idxs, right) - br(idxs, left - 1) >= threshold:
                return x

        return -1
    

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.indices = defaultdict(list)
        for a in set(arr):
            self.indices[a].append(-1)
        for i, a in enumerate(arr):
            self.indices[a].append(i)
        self.a = list(self.indices.keys())
    def query(self, left: int, right: int, threshold: int) -> int:
        def bs(arr, l, r, target):
            while l<=r:
                m = l+(r-l)//2
                if arr[m]<=target:
                    l = m+1
                else:
                    r = m-1
            return r
        
        for _ in range(20):
            a = random.choice(self.a)
            lst = self.indices[a]
            l, r = bs(lst, 0, len(lst)-1, left-1), bs(lst, 0, len(lst)-1, right)
            if r-l>=threshold:
                return a
        
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.idxes = collections.defaultdict(list)
        for (i, n) in enumerate(arr):
            self.idxes[n].append(i)
        self.arr = arr
        self.st = SegmentTree(len(arr), arr, self.idxes)

    def query(self, left: int, right: int, threshold: int) -> int:
        maj = self.st.query_maj(left, right)
        if maj:
            l, r = bisect.bisect_left(self.idxes[maj], left), bisect.bisect(self.idxes[maj], right)
            if r - l >= threshold:
                return maj
        return -1

class SegmentTree:
    
    def __init__(self, n, arr, idxes):
        self.root = Node(0, n - 1, arr, idxes)
        
    def query_maj(self, lo, hi):
        return self.root.query_maj(lo, hi)

class Node:
    
    def __init__(self, lo, hi, arr, idxes):
        self.lo, self.hi = lo, hi
        self.lc, self.rc = None, None
        self.arr, self.idxes = arr, idxes
        self.maj = None
        
    def query_maj(self, lo, hi):
        
        def is_maj(n):
            if not n:
                return False
            
            l = bisect.bisect_left(self.idxes[n], lo)
            r = bisect.bisect(self.idxes[n], hi)
            return (r - l << 1) > hi - lo
        
        if lo > hi or self.lo > hi or self.hi < lo:
            return None
        
        if lo <= self.lo <= self.hi <= hi:
            if not self.maj:
                if self.lo == self.hi:
                    self.maj = self.arr[self.lo]
                else:
                    l, r = None, None
                    mi = (self.lo + self.hi) >> 1
                    # Note: we don't need to check whether 'lc' or 'rc' overlap with [lo, hi],
                    # since the parent node is already within [lo, hi]
                    if not self.lc:
                        self.lc = Node(self.lo, mi, self.arr, self.idxes)
                    # Note: we should not query [lo, hi], but instead query [self.lo, mi],
                    # since maj element in [self.lo, mi] may not necessarily be a maj element of [lo, hi],
                    # leading to a false negative
                    l = self.lc.query_maj(self.lo, mi)
                    
                    # Note: same on the 'rc' as on 'lc'
                    if not self.rc:
                        self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
                    r = self.rc.query_maj(mi + 1, self.hi)
                        
                    self.maj = l if is_maj(l) else r if is_maj(r) else -1
            return self.maj
        
        mi = (self.lo + self.hi) >> 1
        l, r = None, None
        if lo <= mi:
            if not self.lc:
                self.lc = Node(self.lo, mi, self.arr, self.idxes)
            l = self.lc.query_maj(max(self.lo, lo), min(mi, hi))
        if mi + 1 <= hi:
            if not self.rc:
                self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
            r = self.rc.query_maj(max(lo, mi + 1), min(self.hi, hi))
        return l if is_maj(l) else r if is_maj(r) else -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.idxes = collections.defaultdict(list)
        for (i, n) in enumerate(arr):
            self.idxes[n].append(i)
        self.arr = arr
        self.st = SegmentTree(len(arr), arr, self.idxes)

    def query(self, left: int, right: int, threshold: int) -> int:
        maj = self.st.query_maj(left, right)
        if maj:
            l, r = bisect.bisect_left(self.idxes[maj], left), bisect.bisect(self.idxes[maj], right)
            if r - l >= threshold:
                return maj
        return -1

class SegmentTree:
    
    def __init__(self, n, arr, idxes):
        self.root = Node(0, n - 1, arr, idxes)
        
    def query_maj(self, lo, hi):
        return self.root.query_maj(lo, hi)

class Node:
    
    def __init__(self, lo, hi, arr, idxes):
        self.lo, self.hi = lo, hi
        self.lc, self.rc = None, None
        self.arr, self.idxes = arr, idxes
        self.maj = None
        
    def query_maj(self, lo, hi):
        
        def is_maj(n):
            if not n:
                return False
            
            l = bisect.bisect_left(self.idxes[n], lo)
            r = bisect.bisect(self.idxes[n], hi)
            return (r - l << 1) > hi - lo
        
        if lo > hi or self.lo > hi or self.hi < lo:
            return None
        
        if lo <= self.lo <= self.hi <= hi:
            if not self.maj:
                if self.lo == self.hi:
                    self.maj = self.arr[self.lo]
                else:
                    mi = (self.lo + self.hi) >> 1
                    if not self.lc:
                        self.lc = Node(self.lo, mi, self.arr, self.idxes)
                    if not self.rc:
                        self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
                    l = self.lc.query_maj(self.lo, mi)
                    r = self.rc.query_maj(mi + 1, self.hi)
                    self.maj = l if is_maj(l) else r if is_maj(r) else -1
            return self.maj
        
        mi = (self.lo + self.hi) >> 1
        if not self.lc:
            self.lc = Node(self.lo, mi, self.arr, self.idxes)
        if not self.rc:
            self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
    
        l = self.lc.query_maj(lo, hi)
        r = self.rc.query_maj(lo, hi)
        return l if is_maj(l) else r if is_maj(r) else -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.idxes = collections.defaultdict(list)
        for (i, n) in enumerate(arr):
            self.idxes[n].append(i)
        self.arr = arr
        self.st = SegmentTree(len(arr), arr, self.idxes)

    def query(self, left: int, right: int, threshold: int) -> int:
        maj = self.st.query_maj(left, right)
        if maj:
            l, r = bisect.bisect_left(self.idxes[maj], left), bisect.bisect(self.idxes[maj], right)
            if r - l >= threshold:
                return maj
        return -1

class SegmentTree:
    
    def __init__(self, n, arr, idxes):
        self.root = Node(0, n - 1, arr, idxes)
        
    def query_maj(self, lo, hi):
        return self.root.query_maj(lo, hi)

class Node:
    
    def __init__(self, lo, hi, arr, idxes):
        self.lo, self.hi = lo, hi
        self.lc, self.rc = None, None
        self.arr, self.idxes = arr, idxes
        self.maj = None
        
    def query_maj(self, lo, hi):
        
        def is_maj(n):
            if not n:
                return False
            
            l = bisect.bisect_left(self.idxes[n], lo)
            r = bisect.bisect(self.idxes[n], hi)
            return (r - l << 1) > hi - lo
        
        if lo > hi or self.lo > hi or self.hi < lo:
            return None
        
        if self.lo >= lo and self.hi <= hi:
            if not self.maj:
                if self.lo == self.hi:
                    self.maj = self.arr[self.lo]
                else:
                    mi = (self.lo + self.hi) >> 1
                    if not self.lc:
                        self.lc = Node(self.lo, mi, self.arr, self.idxes)
                    if not self.rc:
                        self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
                    l = self.lc.query_maj(self.lo, mi)
                    r = self.rc.query_maj(mi + 1, self.hi)
                    self.maj = l if is_maj(l) else r if is_maj(r) else -1
            return self.maj
        
        mi = (self.lo + self.hi) >> 1
        if not self.lc:
            self.lc = Node(self.lo, mi, self.arr, self.idxes)
        if not self.rc:
            self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
    
        l = self.lc.query_maj(lo, hi)
        r = self.rc.query_maj(lo, hi)
        return l if is_maj(l) else r if is_maj(r) else -1
        
#         def is_maj(n):
#             if not n:
#                 return False
            
#             l = bisect.bisect_left(self.idxes[n], lo)
#             r = bisect.bisect(self.idxes[n], hi)
#             return (r - l << 1) > hi - lo
        
#         def get_children_maj():
#             l, r = None, None
#             mi = (self.lo + self.hi) >> 1
#             # if lo <= mi:
#             if not self.lc:
#                 self.lc = Node(self.lo, mi, self.arr, self.idxes)
#             l = self.lc.query_maj(lo, hi)
            
#             # if mi + 1 <= hi:
#             if not self.rc:
#                 self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
#             r = self.rc.query_maj(lo, hi)
            
#             return l, r
        
#         if self.lo > hi or self.hi < lo:
#             return None
#         if self.lo == self.hi:
#             return self.arr[self.lo]
        
#         if lo <= self.lo <= self.hi <= hi:
#             # lazy population: initially, 'self.maj' is not set
#             if not self.maj:
#                 # base case: only 1 element in the node
#                 # and that must be the majority element
#                 # if self.lo == self.hi:
#                 #     self.maj = self.arr[self.lo]
#                 # else:
#                     # l, r = get_children_maj()
                    
                    
#                 mi = (self.lo + self.hi) >> 1
#                 # if lo <= mi:
#                 if not self.lc:
#                     self.lc = Node(self.lo, mi, self.arr, self.idxes)
#                 l = self.lc.query_maj(lo, hi)

#                 # if mi + 1 <= hi:
#                 if not self.rc:
#                     self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
#                 r = self.rc.query_maj(lo, hi)


#                 if is_maj(l):
#                     self.maj = l
#                 elif is_maj(r):
#                     self.maj = r
#                 else:
#                     self.maj = -1
#             return self.maj
        
#         # l, r = get_children_maj()
#         # return l if is_maj(l) else r if is_maj(r) else None
#         mi = (self.lo + self.hi) >> 1
#         # if lo <= mi:
#         if not self.lc:
#             self.lc = Node(self.lo, mi, self.arr, self.idxes)
#         l = self.lc.query_maj(lo, hi)

#         # if mi + 1 <= hi:
#         if not self.rc:
#             self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
#         r = self.rc.query_maj(lo, hi)
#         if is_maj(l):
#             return l
#         if is_maj(r):
#             return r
#         return -1




# class Node:
    
#     def __init__(self, lo, hi, arr, cnt):
#         self.lo, self.hi = lo, hi
#         # self.maj: the majority element in range [self.lo, self.hi]
#         self.left, self.right, self.maj = None, None, None
#         self.arr, self.cnt = arr, cnt
    
#     def query(self, lo, hi):
        
#         def isMaj(n):
#             if n:
#                 l, r = bisect.bisect_left(self.cnt[n], lo), bisect.bisect_right(self.cnt[n], hi)
#                 return (r - l) * 2 > hi - lo
#             return False
        
#         if lo > hi or self.lo > hi or self.hi < lo:
#             return None
#         if self.lo == self.hi:
#             return self.arr[self.lo]
        
#         if self.lo >= lo and self.hi <= hi:
#             if not self.maj:
#                 mi = (self.lo + self.hi) >> 1
#                 if not self.left:
#                     self.left = Node(self.lo, mi, self.arr, self.cnt)
#                 if not self.right:
#                     self.right = Node(mi + 1, self.hi, self.arr, self.cnt)
#                 l = self.left.query(self.lo, mi)
#                 r = self.right.query(mi + 1, self.hi)
#                 if l != -1 and isMaj(l):
#                     self.maj = l
#                 elif r != -1 and isMaj(r):
#                     self.maj = r
#                 else:
#                     self.maj = -1
#             return self.maj
        
#         mi = (self.lo + self.hi) >> 1
#         if not self.left:
#             self.left = Node(self.lo, mi, self.arr, self.cnt)
#         if not self.right:
#             self.right = Node(mi + 1, self.hi, self.arr, self.cnt)
    
#         l = self.left.query(lo, hi)
#         r = self.right.query(lo, hi)
#         if l != -1 and isMaj(l):
#             return l
#         if r != -1 and isMaj(r):
#             return r
#         return -1

# class MajorityChecker:

#     def __init__(self, arr: List[int]):
#         self.cnt = collections.defaultdict(list)
#         for (i, v) in enumerate(arr):
#             self.cnt[v] += i,
#         self.arr = arr
#         self.root = Node(0, len(arr) - 1, self.arr, self.cnt)
    
#     def query(self, left: int, right: int, threshold: int) -> int:
#         elm = self.root.query(left, right)
#         if elm != -1:
#             lo, hi = bisect.bisect_left(self.cnt[elm], left), bisect.bisect_right(self.cnt[elm], right)
#             if hi - lo >= threshold:
#                 return elm
#         return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:
    
    def __init__(self, arr: List[int]):
        self.num_to_index = collections.defaultdict(list)
        for x in range(len(arr)):
            self.num_to_index[arr[x]].append(x)
        self.arr = arr
        
    def query(self, left: int, right: int, threshold: int) -> int:
        visited = set()
        length = right - left+1
        for x in range(left,right+1):
            if self.arr[x] in visited:
                continue
            left_i = bisect.bisect_left(self.num_to_index[self.arr[x]],left)
            right_i = bisect.bisect_right(self.num_to_index[self.arr[x]],right)-1
            #print(self.num_to_index[self.arr[x]])
            #print(left_i,right_i,self.arr[x])
            if right_i - left_i+1 >= threshold:
                return self.arr[x]
            #threshold = threshold-(right_i - left_i+1)
            length = length - (right_i - left_i+1)
            if threshold > length:
                return -1
            visited.add(self.arr[x])
        return -1
            
            
        
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        
        
        self.tables = collections.defaultdict(list)
        for i, num in enumerate(arr):
            self.tables[num].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        
        if right - left + 1 < threshold:
            return -1
        for num in self.tables:
            if len(self.tables[num]) < threshold:
                continue
            l = self.leftSearch(self.tables[num], left)
            r = self.rightSearch(self.tables[num], right)
            # print(num, self.tables[num])
            # print(left, right)
            # print(l, r)
            if r-l  >= threshold:
                return num
        return -1
                
        
        
    def leftSearch(self, array, target):
        
        l = 0
        r = len(array)
        while l < r:
            m = (l+r) // 2
            if array[m] < target:
                l = m + 1
            else:
                r = m
        return l
                
        
        
    def rightSearch(self, array, target):
        
        l = 0
        r = len(array)
        while l < r:
            m = (l+r) // 2
            if array[m] <= target:
                l = m + 1
            else:
                r = m
        return l
        
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


import collections as clc
import time

start = time.time()


class SegmentTree:
    
    def __init__(self, left_bound: int, right_bound: int):
        self.left_bound = left_bound
        self.right_bound = right_bound
        self.mid = None
        self.values = None
        self.most_frequent = None
        self.left = None
        self.right = None
        
    def split(self, mid: int):
        self.mid = mid
        self.left = SegmentTree(self.left_bound, self.mid)
        self.right = SegmentTree(self.mid, self.right_bound)
    
    def __len__(self):
        return self.right_bound - self.left_bound

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.arr = arr
        self.tree = SegmentTree(0, self.n)
        self.build(self.tree)
    
    def build(self, node: SegmentTree):
        if len(node) == 1:
            node.values = clc.Counter(self.arr[node.left_bound : node.right_bound])
            node.most_frequent = self.arr[node.left_bound]
            return
        node.split((node.left_bound + node.right_bound) // 2)
        self.build(node.left)
        self.build(node.right)
        node.values = node.left.values + node.right.values
        left_freq = node.left.most_frequent
        right_freq = node.right.most_frequent
        if (
            node.left.values[left_freq] + node.right.values[left_freq]
            >= node.left.values[right_freq] + node.right.values[right_freq]
        ):
            node.most_frequent = left_freq
        else:
            node.most_frequent = right_freq

    def query(self, left: int, right: int, threshold: int) -> int:
        counts_set, most_freqs = self.rec_query(self.tree, left, right + 1)
        for num in most_freqs:
            if sum(counts[num] for counts in counts_set) >= threshold:
                return num
        return -1
    
    def rec_query(self, node: int, left: int, right: int):
        if node.left_bound == left and node.right_bound == right:
            return [node.values], [node.most_frequent]
        if right <= node.mid:
            return self.rec_query(node.left, left, right)
        if left >= node.mid:
            return self.rec_query(node.right, left, right)
        left_values, left_set = self.rec_query(node.left, left, node.mid)
        right_values, right_set = self.rec_query(node.right, node.mid, right)
        return left_values + right_values, left_set + right_set


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


import collections as clc
import time

start = time.time()


class SegmentTree:
    
    def __init__(self, left_bound: int, right_bound: int):
        self.left_bound = left_bound
        self.right_bound = right_bound
        self.mid = None
        self.values = None
        self.most_frequent = None
        self.left = None
        self.right = None
        
    def split(self, mid: int):
        self.mid = mid
        self.left = SegmentTree(self.left_bound, self.mid)
        self.right = SegmentTree(self.mid, self.right_bound)
    
    def __len__(self):
        return self.right_bound - self.left_bound
    
    def __str__(self):
        return f\"[{self.left_bound}, {self.right_bound})({self.left} | {self.mid} | {self.right})\"

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.arr = arr
        self.tree = SegmentTree(0, self.n)
        self.build(self.tree)
    
    def build(self, node: SegmentTree):
        if len(node) == 1:
            node.values = clc.Counter(self.arr[node.left_bound : node.right_bound])
            node.most_frequent = self.arr[node.left_bound]
            return
        node.split((node.left_bound + node.right_bound) // 2)
        self.build(node.left)
        self.build(node.right)
        node.values = node.left.values + node.right.values
        node.most_frequent = node.values.most_common(1)[0][0]

    def query(self, left: int, right: int, threshold: int) -> int:
        counts_set, most_freqs = self.rec_query(self.tree, left, right + 1)
        for num in most_freqs:
            if sum(counts[num] for counts in counts_set) >= threshold:
                return num
        return -1
    
    def rec_query(self, node: int, left: int, right: int):
        if node.left_bound == left and node.right_bound == right:
            return [node.values], {node.most_frequent}
        if right <= node.mid:
            return self.rec_query(node.left, left, right)
        if left >= node.mid:
            return self.rec_query(node.right, left, right)
        left_values, left_set = self.rec_query(node.left, left, node.mid)
        right_values, right_set = self.rec_query(node.right, node.mid, right)
        return left_values + right_values, left_set | right_set


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.idxes = collections.defaultdict(list)
        for (i, n) in enumerate(arr):
            self.idxes[n].append(i)
        self.arr = arr
        self.st = SegmentTree(len(arr), arr, self.idxes)

    def query(self, left: int, right: int, threshold: int) -> int:
        maj = self.st.query_maj(left, right)
        if maj:
            l, r = bisect.bisect_left(self.idxes[maj], left), bisect.bisect(self.idxes[maj], right)
            if r - l >= threshold:
                return maj
        return -1

class SegmentTree:
    
    def __init__(self, n, arr, idxes):
        self.root = Node(0, n - 1, arr, idxes)
        
    def query_maj(self, lo, hi):
        return self.root.query_maj(lo, hi)

class Node:
    
    def __init__(self, lo, hi, arr, idxes):
        self.lo, self.hi = lo, hi
        self.lc, self.rc = None, None
        self.arr, self.idxes = arr, idxes
        self.maj = None
        
    def query_maj(self, lo, hi):
        
        def is_maj(n):
            if not n:
                return False
            
            l = bisect.bisect_left(self.idxes[n], lo)
            r = bisect.bisect(self.idxes[n], hi)
            return (r - l << 1) > hi - lo
        
        if lo > hi or self.lo > hi or self.hi < lo:
            return None
        
        if lo <= self.lo <= self.hi <= hi:
            if not self.maj:
                if self.lo == self.hi:
                    self.maj = self.arr[self.lo]
                else:
                    l, r = None, None
                    mi = (self.lo + self.hi) >> 1
                    if lo <= mi:
                        if not self.lc:
                            self.lc = Node(self.lo, mi, self.arr, self.idxes)
                        l = self.lc.query_maj(self.lo, mi)
                    if mi <= hi:
                        if not self.rc:
                            self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
                        r = self.rc.query_maj(mi + 1, self.hi)
                        
                    self.maj = l if is_maj(l) else r if is_maj(r) else -1
            return self.maj
        
        mi = (self.lo + self.hi) >> 1
        if not self.lc:
            self.lc = Node(self.lo, mi, self.arr, self.idxes)
        if not self.rc:
            self.rc = Node(mi + 1, self.hi, self.arr, self.idxes)
    
        l = self.lc.query_maj(lo, hi)
        r = self.rc.query_maj(lo, hi)
        return l if is_maj(l) else r if is_maj(r) else -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import defaultdict
import bisect
class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr=arr
        self.pos=defaultdict(list)
        self.count=defaultdict(int)
        for i in range(len(arr)):
            item=arr[i]
            self.pos[item].append(i)
            self.count[item]+=1
        self.rank=sorted(list(self.count.keys()),key=lambda x: self.count[x],reverse=True)
        

    def query(self, left: int, right: int, threshold: int) -> int:
        
        if right-left<40:
            dp=defaultdict(int)
            for i in range(left,right+1):
                dp[self.arr[i]]+=1
            element= max(list(dp.keys()),key=lambda x: dp[x])
            if dp[element]>=threshold:
                return element
            else:
                return -1
        else:
            for item in self.rank:
                if self.count[item]>=threshold:
                    l1=bisect.bisect_left(self.pos[item],left)
                    l2=bisect.bisect_right(self.pos[item],right)
                    if l2-l1>=threshold:
                        return item
                else:
                    break
            return -1
                        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


import collections as clc
import time

start = time.time()


class SegmentTree:
    
    def __init__(self, left_bound: int, right_bound: int):
        self.left_bound = left_bound
        self.right_bound = right_bound
        self.mid = None
        self.values = None
        self.most_frequent = None
        self.left = None
        self.right = None
        
    def split(self, mid: int):
        self.mid = mid
        self.left = SegmentTree(self.left_bound, self.mid)
        self.right = SegmentTree(self.mid, self.right_bound)
    
    def __len__(self):
        return self.right_bound - self.left_bound

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.arr = arr
        self.tree = SegmentTree(0, self.n)
        self.build(self.tree)
    
    def build(self, node: SegmentTree):
        if len(node) == 1:
            node.values = clc.Counter(self.arr[node.left_bound : node.right_bound])
            node.most_frequent = self.arr[node.left_bound]
            return
        node.split((node.left_bound + node.right_bound) // 2)
        self.build(node.left)
        self.build(node.right)
        node.values = node.left.values + node.right.values
        node.most_frequent = node.values.most_common(1)[0][0]

    def query(self, left: int, right: int, threshold: int) -> int:
        counts_set, most_freqs = self.rec_query(self.tree, left, right + 1)
        for num in most_freqs:
            if sum(counts[num] for counts in counts_set) >= threshold:
                return num
        return -1
    
    def rec_query(self, node: int, left: int, right: int):
        if node.left_bound == left and node.right_bound == right:
            return [node.values], [node.most_frequent]
        if right <= node.mid:
            return self.rec_query(node.left, left, right)
        if left >= node.mid:
            return self.rec_query(node.right, left, right)
        left_values, left_set = self.rec_query(node.left, left, node.mid)
        right_values, right_set = self.rec_query(node.right, node.mid, right)
        return left_values + right_values, left_set + right_set


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


import random
class St:
    class Node:
        def __init__(self, vals):
            self.vals = vals
            self.stat = None     
            self.left = None
            self.right = None
    
    def __init__(self, arr):
        self.arr = arr
        self.root = self.build(0, len(self.arr)-1)
        
    def build(self, i, j):
        if i == j:
            N = St.Node((i,j))
            N.stat = collections.Counter([self.arr[i]])
            return N
        
        N = St.Node((i,j))
        k = (i+j)>>1
        N.left = self.build(i, k)
        N.right = self.build(k+1, j)

        N.stat = N.left.stat + N.right.stat
        
        return N        
    
    def retriveStat(self, i, j, t):
        sentinel = False
        res = self.root.stat.copy() # this could be run in a separate thread
        
        def helper(node):
            nonlocal i,j,t,res,sentinel
            if sentinel:
                res = dict()
                return        
            if not res or max(res.values()) < t:
                res = dict()
                sentinel = True
                return
            
            l,r = node.vals
            
            if r < i or l > j:
                res -= node.stat
                return
                
            if i <= l and r <= j:
                return
            
            if l != r:
                helper(node.left)
                helper(node.right)
            
        helper(self.root)
        
        if not res:
            return -1
        
        m = max(res, key=lambda x:res[x])
        return m if res[m] >= t else -1

class MajorityChecker:
    
    def __init__(self, arr: List[int]):
        self.arr = arr
        self.StO = St(arr)

    def query(self, left: int, right: int, threshold: int) -> int:
        return self.StO.retriveStat(left, right, threshold)

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

# import random
# class MajorityChecker:
#     def _get_rand_pos(self, left, right):
#         for e in random.sample(range(left,right+1), right-left+1):
#             yield e

#     def __init__(self, arr: List[int]):
#         self.arr = arr

#     def query(self, left: int, right: int, threshold: int) -> int:
#         l = right - left
#         MC = 0
#         ME = None
#         D = collections.defaultdict(int)
#         for i in self._get_rand_pos(left,right):
#             D[self.arr[i]] += 1
#             if MC < D[self.arr[i]]:
#                 MC = D[self.arr[i]]
#                 ME = self.arr[i]
#                 if MC >= threshold:
#                     return ME
#         return ME if MC >= threshold else -1


# import random
# class St:
#     class Node:
#         def __init__(self, vals):
#             self.vals = vals
#             self.stat = None     
#             self.left = None
#             self.right = None
    
#     def __init__(self, arr):
#         self.arr = arr
#         self.root = self.build(0, len(self.arr)-1)
        
#     def build(self, i, j):
#         if i == j:
#             N = St.Node((i,j))
#             N.stat = collections.Counter([self.arr[i]])
#             return N
        
#         N = St.Node((i,j))
#         k = (i+j)>>1
#         N.left = self.build(i, k)
#         N.right = self.build(k+1, j)

#         N.stat = N.left.stat + N.right.stat
        
#         return N        
    
#     def retriveStat(self, i, j, t):
#         sentinel = False
#         res = self.root.stat.copy()
        
#         def helper(node):
#             nonlocal i,j,t,res,sentinel
#             if sentinel:
#                 res = dict()
#                 return        
#             if not res or max(res.values()) < t:
#                 res = dict()
#                 sentinel = True
#                 return
            
#             l,r = node.vals
            
#             if r < i or l > j:
#                 res -= node.stat
#                 return
                
#             if l > j or i > r:
#                 return
#             if node.left:helper(node.left)
#             if node.right:helper(node.right)
            
#         helper(self.root)
#         return res.most_common()[0] if res else (-1,-1)

# class MajorityChecker:
    
#     def __init__(self, arr: List[int]):
#         self.arr = arr
#         self.StO = St(arr)

#     def query(self, left: int, right: int, threshold: int) -> int:
#         R = self.StO.retriveStat(left, right, threshold)
#         return R[0] if R[1] >= threshold else -1


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.numDict = defaultdict(list)
        for i, num in enumerate(arr):
            self.numDict[num].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        leftCandi = right - left + 1
        iNow = right
        visited = set()
        while leftCandi >= threshold:
            if self.arr[iNow] not in visited:
                visited.add(self.arr[iNow])
                numOfINow  = self.count(iNow, left)
                if numOfINow >= threshold:
                    return self.arr[iNow]
                else:
                    leftCandi -= numOfINow
            iNow -= 1
        return -1
    
    def count(self, i0, left):
        num = self.arr[i0]
        listLen = len(self.numDict[num])
        l = 0
        r = listLen - 1
        if i0 == self.numDict[num][r]:
            right  = r
        elif i0 == self.numDict[num][l]:
            right = l
        else:
            while r > l:
                m = (r + l) // 2
                if self.numDict[num][m] < i0:
                    l = m + 1
                elif self.numDict[num][m] > i0:
                    r = m
                else:
                    l = m
                    r = l -1
            right = l
        l = 0 
        r = right
        if left <= self.numDict[num][l]:
            return right + 1
        # if left == self.numDict[num][r]:
        #     return 1
        while r > l:
            m = (r + l) // 2
            if self.numDict[num][m] < left:
                l = m + 1
            else:#if self.numDict[num][m] > left:
                r = m
            # else:
            #     return right - m +1
        return right- l + 1
        
        
        
    
    
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

# class MajorityChecker:

#     def __init__(self, arr: List[int]):
#         preIndexDict = {}
#         arrLen = len(arr)
#         self.preIndexList = [i for i in range(arrLen)]
#         self.arr = arr
#         for i, num in enumerate(arr):
#             if num in preIndexDict:
#                 self.preIndexList[i] = preIndexDict[num]
#             preIndexDict[num] = i
#         self.dp = {}

#     def query(self, left: int, right: int, threshold: int) -> int:
#         leftCandi = right - left + 1
#         iNow = right
#         visited = set()
#         while leftCandi >= threshold:
#             if self.arr[iNow] not in visited:
#                 visited.add(self.arr[iNow])
#                 numOfINow  = self.count(iNow, left)
#                 if numOfINow >= threshold:
#                     return self.arr[iNow]
#                 else:
#                     leftCandi -= numOfINow
#             iNow -= 1
#         return -1
                
#     def count(self, i0, l):
#         if (i0, l) in self.dp:
#             return self.dp[(i0,l)]
#         if self.preIndexList[i0] == i0 or self.preIndexList[i0] < l:
#             return 1
#         self.dp[(i0,l)] = 1 + self.count(self.preIndexList[i0], l)
#         return self.dp[(i0,l)]


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.prearr = [[] for _ in range(max(arr)+1)]
        
        for i in range (len(arr)):
                self.prearr[arr[i]].append(i) 
            
    def query(self, left: int, right: int, threshold: int) -> int:   
        
        def checkmajority (k):
            
            #find index of left element 
            lo = 0 
            hi= len(self.prearr[k])-1
            
            while (lo<hi):
                mid = lo +((hi-lo)//2)
                
                if (self.prearr[k][mid]>=left):
                    hi = mid 
                    
                else:
                    lo = mid+1
                    
            start = lo
            
            #find index of right element 
            lo = 0 
            hi = len(self.prearr[k])-1
            
            while(lo<hi):
                mid = lo + ((hi-lo +1)//2)
                
                if(self.prearr[k][mid] <= right):
                    lo = mid
                else:
                    hi = mid-1 
            end = lo 
            
            # return the difference between indexes between the preaar element and compare it with threshold 
            
            if ((end - start +1) >= threshold): 
                return (True)
            
            else:
                return (False)
            
            
        #pick random element from arr 30-50 times and check if it is majority or not
        
        res = False
        a = self.arr[left:right+1]
        
        for _ in range (10): 
            k = random.choice(a)
            res = res or checkmajority(k)
            
            if (res):
                return(k)
        
        return(-1)      
        
        

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.numDict = defaultdict(list)
        for i, num in enumerate(arr):
            self.numDict[num].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        leftCandi = right - left + 1
        iNow = right
        visited = set()
        while leftCandi >= threshold:
            if self.arr[iNow] not in visited:
                visited.add(self.arr[iNow])
                numOfINow  = self.count(iNow, left)
                if numOfINow >= threshold:
                    return self.arr[iNow]
                else:
                    leftCandi -= numOfINow
            iNow -= 1
        return -1
    
    def count(self, i0, left):
        num = self.arr[i0]
        listLen = len(self.numDict[num])
        l = 0
        r = listLen - 1
        if i0 == self.numDict[num][r]:
            right  = r
        elif i0 == self.numDict[num][l]:
            right = l
        else:
            while r > l:
                m = (r + l) // 2
                if self.numDict[num][m] < i0:
                    l = m + 1
                elif self.numDict[num][m] > i0:
                    r = m
                else:
                    l = m
                    r = l -1
            right = l
        l = 0 
        r = right
        if left <= self.numDict[num][l]:
            return right + 1
        if left == self.numDict[num][r]:
            return 1
        while r > l:
            m = (r + l) // 2
            if self.numDict[num][m] < left:
                l = m + 1
            else:#if self.numDict[num][m] > left:
                r = m
            # else:
            #     return right - m +1
        return right- l + 1
        
        
        
    
    
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

# class MajorityChecker:

#     def __init__(self, arr: List[int]):
#         preIndexDict = {}
#         arrLen = len(arr)
#         self.preIndexList = [i for i in range(arrLen)]
#         self.arr = arr
#         for i, num in enumerate(arr):
#             if num in preIndexDict:
#                 self.preIndexList[i] = preIndexDict[num]
#             preIndexDict[num] = i
#         self.dp = {}

#     def query(self, left: int, right: int, threshold: int) -> int:
#         leftCandi = right - left + 1
#         iNow = right
#         visited = set()
#         while leftCandi >= threshold:
#             if self.arr[iNow] not in visited:
#                 visited.add(self.arr[iNow])
#                 numOfINow  = self.count(iNow, left)
#                 if numOfINow >= threshold:
#                     return self.arr[iNow]
#                 else:
#                     leftCandi -= numOfINow
#             iNow -= 1
#         return -1
                
#     def count(self, i0, l):
#         if (i0, l) in self.dp:
#             return self.dp[(i0,l)]
#         if self.preIndexList[i0] == i0 or self.preIndexList[i0] < l:
#             return 1
#         self.dp[(i0,l)] = 1 + self.count(self.preIndexList[i0], l)
#         return self.dp[(i0,l)]


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.numDict = defaultdict(list)
        for i, num in enumerate(arr):
            self.numDict[num].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        leftCandi = right - left + 1
        iNow = right
        visited = set()
        while leftCandi >= threshold:
            if self.arr[iNow] not in visited:
                visited.add(self.arr[iNow])
                numOfINow  = self.count(iNow, left)
                if numOfINow >= threshold:
                    return self.arr[iNow]
                else:
                    leftCandi -= numOfINow
            iNow -= 1
        return -1
    
    def count(self, i0, left):
        num = self.arr[i0]
        listLen = len(self.numDict[num])
        l = 0
        r = listLen - 1
        if i0 == self.numDict[num][r]:
            right  = r
        elif i0 == self.numDict[num][l]:
            right = l
        else:
            while r > l:
                m = (r + l) // 2
                if self.numDict[num][m] < i0:
                    l = m + 1
                elif self.numDict[num][m] > i0:
                    r = m
                else:
                    l = m
                    r = l -1
            right = l
        l = 0 
        r = right
        if left <= self.numDict[num][l]:
            return right + 1
        if left == self.numDict[num][r]:
            return 1
        while r > l:
            m = (r + l) // 2
            if self.numDict[num][m] < left:
                l = m + 1
            elif self.numDict[num][m] > left:
                r = m
            else:
                return right - m +1
        return right- l + 1
        
        
        
    
    
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

# class MajorityChecker:

#     def __init__(self, arr: List[int]):
#         preIndexDict = {}
#         arrLen = len(arr)
#         self.preIndexList = [i for i in range(arrLen)]
#         self.arr = arr
#         for i, num in enumerate(arr):
#             if num in preIndexDict:
#                 self.preIndexList[i] = preIndexDict[num]
#             preIndexDict[num] = i
#         self.dp = {}

#     def query(self, left: int, right: int, threshold: int) -> int:
#         leftCandi = right - left + 1
#         iNow = right
#         visited = set()
#         while leftCandi >= threshold:
#             if self.arr[iNow] not in visited:
#                 visited.add(self.arr[iNow])
#                 numOfINow  = self.count(iNow, left)
#                 if numOfINow >= threshold:
#                     return self.arr[iNow]
#                 else:
#                     leftCandi -= numOfINow
#             iNow -= 1
#         return -1
                
#     def count(self, i0, l):
#         if (i0, l) in self.dp:
#             return self.dp[(i0,l)]
#         if self.preIndexList[i0] == i0 or self.preIndexList[i0] < l:
#             return 1
#         self.dp[(i0,l)] = 1 + self.count(self.preIndexList[i0], l)
#         return self.dp[(i0,l)]


import collections
class StNode:
    def __init__(self, left, right):
        self.left = None
        self.right = None
        self.stats = None
        self.vals = (left, right)

class St:
    def __init__(self, arr):
        self.arr = arr
        self.root = self.build(0, len(arr)-1)
    def build(self, i, j):
        if i == j:
            N = StNode(i,j)
            N.stats = collections.Counter([self.arr[i]])
            return N
        
        k = (i + j) >> 1
        
        N = StNode(i,j)
        
        N.left = self.build(i,k)
        N.right = self.build(k+1,j)
        
        N.stats = N.left.stats + N.right.stats
        
        return N
        
    def retrieveLargestStats(self, i, j, t):
        
        R = self.root.stats.copy()
        abort = False        
        
        def helper(node):
            nonlocal abort, R, i, j, t
            if abort:
                return
            if not R or max(R.values()) < t:
                abort = True
                R = dict()
                return
            
            l,r = node.vals
            
            if i > r or l > j:
                R -= node.stats
                return
            
            if i <= l and r <= j:
                return
            
            if l == r:
                return
            
            helper(node.left)
            helper(node.right)
        
        helper(self.root)
        
        if not R:
            return -1
        
        m = max(R, key=lambda x:R[x])
        return m if R[m] >=t else -1
        

class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.ST = St(arr)

    def query(self, left: int, right: int, threshold: int) -> int:
        return self.ST.retrieveLargestStats(left, right, threshold)


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import Counter

class Node(object):
    '''
    Node of the segment tree.  
    
    self.val = [i,j] where i and j are lower and upper bound indices in array (arr)
    self.count = Counter(arr[i:j+1])  <-- keeps track of the frequency of each value in the range [i,j] inclusive
    '''
    def __init__(self,val):
        self.val = val
        self.count = None

class Segment_Tree(object):
    def __init__(self, arr):
        self.arr = arr
        self.root = self.build(0,len(arr)-1)
        
    def build(self, i, j):
        '''
        constructs segment tree where each node has:
        
            1. a value of the index range [i,j] (inclusive) that it covers
            2. a counter for how many times each number appears in the range [i,j]j
            
        *Note, self.root will look like:
        
            self.root.val = [0, len(arr) - 1]
            self.root.count = Counter(arr)
        '''
        
        if i == j:
            node = Node([i,i])
            node.count = Counter([self.arr[i]])
            return node
        
        node = Node([i,j])
        k = (i+j)>>1
        node.left = self.build(i,k)
        node.right = self.build(k+1,j)
        
        node.count = node.left.count + node.right.count
        
        return node
        

    def find_most_common(self, l, r, threshold):
        '''
        returns a tuple of (most common element, frequency) in the range l, r
        where 0 <= l <= r < self.arr.length
        
        This is done as a subtraction process:
        
            1. res = self.root.count.copy()  <-- equivalent to Counter(arr)
            2. subtract values from res for ranges that are not included in l, r
            3. During this process, if the most frequent value in res ever occurs
               less than treshold times, then trigger the sentinel to quit out
            4. If a range [i,j] on the tree is completely contained within [l,r] inclusive
               then do not subtract the values in A[i:j+1] from the result
        '''
        
        res = self.root.count.copy()
        
        sentinel = False #3
        
        def helper(node):
            nonlocal res, l, r, sentinel, threshold
            
            if sentinel: return None #3
            
            if (not res) or max(res.values()) < threshold: #3
                #there is no solution so set res = {} and escape recursive function
                sentinel = True
                res = {} 
                return None

            i, j = node.val
            if (j < l) or (i > r): #2
                #this node has only values that are OUTSIDE of [left,right] so subtract them from res
                res -= node.count
                return None
            
            if (l <= i) and (j <= r): #4
                #this node has only values that are INSIDE of [left,right] so keep the values
                return None

            helper(node.left)
            helper(node.right)
        
        helper(self.root)
        most_common = max(res, key = lambda k: res[k]) if res else (-1,-1)
        
        return (most_common, res[most_common]) if res else most_common
        

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.tree = Segment_Tree(arr)

    def query(self, left: int, right: int, threshold: int) -> int:
        #Find the value (val) that occurs the most frequently in range [left,right]
        val, freq = self.tree.find_most_common(left, right, threshold)
        return val if freq >= threshold else -1



# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.prearr = [[] for _ in range(max(arr)+1)]
        
        for i in range (len(arr)):
                self.prearr[arr[i]].append(i) 
            
    def query(self, left: int, right: int, threshold: int) -> int:   
        
        def checkmajority (k):
            
            #find index of left element 
            lo = 0 
            hi= len(self.prearr[k])-1
            
            while (lo<hi):
                mid = lo +((hi-lo)//2)
                
                if (self.prearr[k][mid]>=left):
                    hi = mid 
                    
                else:
                    lo = mid+1
                    
            start = lo
            
            #find index of right element 
            lo = 0 
            hi = len(self.prearr[k])-1
            
            while(lo<hi):
                mid = lo + ((hi-lo +1)//2)
                
                if(self.prearr[k][mid] <= right):
                    lo = mid
                else:
                    hi = mid-1 
            end = lo 
            
            # return the difference between indexes between the preaar element and compare it with threshold 
            
            if ((end - start +1) >= threshold): 
                return (True)
            
            else:
                return (False)
            
            
        #pick random element from arr 30-50 times and check if it is majority or not
        
        res = False
        a = self.arr[left:right+1]
        
        for _ in range (15): 
            k = random.choice(a)
            res = res or checkmajority(k)
            
            if (res):
                return(k)
        
        return(-1)      
        
        

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, A):
        a2i = collections.defaultdict(list)
        for i, x in enumerate(A):
            a2i[x].append(i)
        self.a, self.a2i = A, a2i
    
        

    def query(self, left: int, right: int, threshold: int) -> int:
        
        track = self.a2i
                
        l,r = left,right
        
        if((r-l+1) % 2 == 0):
            mid = l-1 + (r-l+1)//2
            
        else:
            mid = l + (r-l+1)//2
            
        
        if((r-mid+1) % 2 == 0):
            mid1 = mid-1 + (r-mid+1)//2
            
        else:
            mid1 = mid + (r-mid+1)//2
        
        if((mid-l+1) % 2 == 0):
            mid2 = l-1 + (mid-l+1)//2
            
        else:
            mid2 = l + (mid-l+1)//2
        
        t1 = bisect.bisect_left(track[self.a[mid]],left)
        t2 = bisect.bisect_right(track[self.a[mid]],right)
        
        if(t2-t1 >= threshold):
            return self.a[mid]
        
        t1 = bisect.bisect_left(track[self.a[mid1]],left)
        t2 = bisect.bisect_right(track[self.a[mid1]],right)
        
        if(t2-t1 >= threshold):
            return self.a[mid1]
        
        t1 = bisect.bisect_left(track[self.a[mid2]],left)
        t2 = bisect.bisect_right(track[self.a[mid2]],right)
        
        if(t2-t1 >= threshold):
            return self.a[mid2]
        
        return -1
        
       
                


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.prearr = [[] for _ in range(max(arr)+1)]
        
        for i in range (len(arr)):
            try:
                self.prearr[arr[i]].append(i) 
            except:
                print((arr[i],len(self.prearr),max(arr)))
            
    def query(self, left: int, right: int, threshold: int) -> int:   
        prearr = self.prearr
        
        def checkmajority (k):
            
            #find index of left element 
            lo = 0 
            hi= len(prearr[k])-1
            
            while (lo<hi):
                mid = lo +((hi-lo)//2)
                
                if (prearr[k][mid]>=left):
                    hi = mid 
                    
                else:
                    lo = mid+1
                    
            start = lo
            
            #find index of right element 
            lo = 0 
            hi = len(prearr[k])-1
            
            while(lo<hi):
                mid = lo + ((hi-lo +1)//2)
                
                if(prearr[k][mid] <= right):
                    lo = mid
                else:
                    hi = mid-1 
            end = lo 
            
            # return the difference between indexes between the preaar element and compare it with threshold 
            
            if ((end - start +1) >= threshold): 
                return (True)
            
            else:
                return (False)
            
            
        #pick random element from arr 30-50 times and check if it is majority or not
        
        res = False
        a = self.arr[left:right+1]
        
        for _ in range (20): 
            k = random.choice(a)
            res = res or checkmajority(k)
            
            if (res):
                return(k)
        
        return(-1)      
        
        

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import Counter, defaultdict
class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.dic = defaultdict()

    def query(self, left: int, right: int, threshold: int) -> int:
        if (left,right) in self.dic:
            if self.dic[(left, right)][1] >= threshold:
                return self.dic[(left, right)][0]
            else:
                return -1
        sub = self.arr[left:right + 1]
        dic = Counter(sub)
        sum_f = 0
        for ele, freq in list(dic.items()):
            if freq >= threshold:
                self.dic[(left, right)] = (ele, freq)
                return ele
            sum_f += freq
            if sum_f > threshold:
                return -1
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.prearr = [[] for _ in range(max(arr)+1)]
        
        for i in range (len(arr)):
                self.prearr[arr[i]].append(i) 
            
    def query(self, left: int, right: int, threshold: int) -> int:   
        
        def checkmajority (k):
            
            #find index of left element 
            lo = 0 
            hi= len(self.prearr[k])-1
            
            while (lo<hi):
                mid = lo +((hi-lo)//2)
                
                if (self.prearr[k][mid]>=left):
                    hi = mid 
                    
                else:
                    lo = mid+1
                    
            start = lo
            
            #find index of right element 
            lo = 0 
            hi = len(self.prearr[k])-1
            
            while(lo<hi):
                mid = lo + ((hi-lo +1)//2)
                
                if(self.prearr[k][mid] <= right):
                    lo = mid
                else:
                    hi = mid-1 
            end = lo 
            
            # return the difference between indexes between the preaar element and compare it with threshold 
            
            if ((end - start +1) >= threshold): 
                return (True)
            
            else:
                return (False)
            
            
        #pick random element from arr 30-50 times and check if it is majority or not
        
        res = False
        a = self.arr[left:right+1]
        
        for _ in range (20): 
            k = random.choice(a)
            res = res or checkmajority(k)
            
            if (res):
                return(k)
        
        return(-1)      
        
        

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


import random
class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.fre = {i:[] for i in set(arr)}
        for i in range(len(arr)):
            self.fre[arr[i]].append(i)


    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(50):
            i = left + random.randint(0,right-left)
            low = self.bsl(self.fre[self.arr[i]],left)
            high = self.bsr(self.fre[self.arr[i]],right)
            if low == -1 or high == -1:
                continue
            if high-low+1>=threshold:
                return self.arr[i]
        return -1

    def bsl(self,arr,n):
        low = 0
        high = len(arr)-1
        while low < high:
            mid = low+(high-low)//2
            if arr[mid]>=n:
                high = mid
            else:
                low = mid+1
        if arr[low] >= n:
            return low
        return -1

    def bsr(self,arr,n):
        low = 0
        high = len(arr)-1
        while low < high:
            mid = low+(high-low+1)//2
            if arr[mid]>n:
                high = mid-1
            else:
                low = mid
        if arr[low] <= n:
            return low
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


import random
class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.fre = {i:[] for i in set(arr)}
        for i in range(len(arr)):
            self.fre[arr[i]].append(i)


    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(50):
            i = left + random.randint(0,right-left)
            low = self.bs(self.fre[self.arr[i]],left)
            if self.fre[self.arr[i]][low] < left:
                low +=1
            high = self.bs(self.fre[self.arr[i]],right)
            if high-low+1>=threshold:
                return self.arr[i]
        return -1
    
    def bs(self,arr,n):
        low = 0
        high = len(arr)-1
        while low < high:
            mid = low+(high-low+1)//2
            if arr[mid]<=n:
                low = mid
            else:
                high = mid-1
        return low

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


from collections import Counter
class Node:
    def __init__(self, l, r, num, time, left=None, right=None):
        self.l = l
        self.r = r
        self.num = num
        self.time = time
        self.left = left
        self.right = right
    

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.t = self.build(0, len(arr)-1)
    
    def build(self, l, r):
        if l == r:
            return Node(l, r, self.arr[l], 1)
        
        mid = (r+l)//2
        num, time = -1, 0
        ln, rn = self.build(l, mid), self.build(mid+1, r)
        for n in [ln, rn]:
            if n:
                if n.num == num:
                    time += n.time
                else:
                    if time > n.time:
                        time -= n.time
                    else:
                        num = n.num
                        time = n.time - time
                    
        return Node(l, r, num, time, ln, rn)
    
    def trange(self, l, r, n):
        if l > r:
            return (-1, 0)
        
        if l == n.l and r == n.r:
            return (n.num, n.time)
        
        mid = (n.r + n.l) // 2
        if r < mid:
            return self.trange(l, r, n.left)
        elif l > mid:
            return self.trange(l, r, n.right)
        
        num, time = -1, 0
        for n, t in [self.trange(l, mid, n.left), self.trange(mid+1, r, n.right)]:
            if n == num:
                time += t
            else:
                if time > t:
                    time -= t
                else:
                    num = n
                    time = t - time
        return num, time


    def query(self, left: int, right: int, threshold: int) -> int:
        x, _ = self.trange(left, right, self.t)
        if self.arr[left:right+1].count(x) >= threshold:
            return x
        return -1


from collections import Counter
class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.arr = arr
        self.min_arr_len = len(arr) // 2
        self.main = Counter(arr)
        self.subarrs = {}
        max_repeats = max(self.main.values())
        max_idx = list(self.main.values()).index(max_repeats)
        self.rets = {(0, len(arr)-1): (max_repeats,
                                       list(self.main.keys())[max_idx])}

    def query(self, left: int, right: int, threshold: int) -> int:
        # check if return value has already been calculated
        if (left, right) in self.rets:
            if self.rets[(left, right)][0] >= threshold:
                print(\"Getting return val from cache...\")
                return self.rets[(left, right)][1]

        targarr = self.arr[left:right+1]
        if len(targarr) > self.min_arr_len:
            # count the new sub-array using main counter
            # this should always be less than O(n)
            self.subarrs[left] = {right: self.main.copy()} 
            if left > 0:
                for num in self.arr[0:left]:
                    self.subarrs[left][right][num] -= 1
            if right < len(self.arr) - 1:
                for num in self.arr[right+1:]:
                    self.subarrs[left][right][num] -= 1
        else:
            # try to create subarray from existing array
            if left in self.subarrs:
                largest = max(self.subarrs[left].keys())
                min_len = ((largest + 1) - left) // 2
                if len(targarr) < (largest+1)-left and len(targarr) > min_len:
                    self.subarrs[left][right] = self.subarrs[left][largest]
                    for num in self.arr[right+1:largest+1]:
                        self.subarrs[left][right][num] -= 1
                else:
                    self.subarrs[left][right] = Counter(targarr)
            else:
                self.subarrs[left] = {right: Counter(targarr)}
            
        # get the most repeated number and the no. of repeats
        subarr_vals = list(self.subarrs[left][right].values())
        max_repeats = max(subarr_vals)
        max_idx = subarr_vals.index(max_repeats)
        repeat_num = list(self.subarrs[left][right].keys())[max_idx]
        # save result
        self.rets[(left, right)] = (max_repeats, repeat_num)
        
        if self.rets[(left, right)][0] >= threshold:
            return self.rets[(left, right)][1]
        
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

from bisect import bisect_left, bisect_right
class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.dic = defaultdict(list)
        for i,e in enumerate(arr):
            self.dic[e].append(i)
        self.nums = sorted(self.dic, key=lambda x:len(self.dic[x]), reverse=True)

    def query(self, left: int, right: int, threshold: int) -> int:
        # try all nums
        # 1 2 4 6
        # 1 4
        # see how many times each appears in range
        for num in self.nums:
            # find where first and last occurrence are
            entry = self.dic[num]
            if len(entry) < threshold:
                return -1
            l, r = bisect_left(entry, left), bisect_right(entry, right)
            if r-l >= threshold:
                return num
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        
        self.idx = collections.defaultdict(list)
        for i,a in enumerate(arr):
            self.idx[a].append(i)
        
        print((self.idx))

    def query(self, left: int, right: int, threshold: int) -> int:
        
        for k,v in list(self.idx.items()):
            l = bisect.bisect_left(v, left)
            r = bisect.bisect_right(v, right)
            if r-l >= threshold:
                return k
        
        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.counts = [Counter() for _ in range(self.n * 2)]
        for i, num in enumerate(arr):
            self.counts[i + self.n][num] += 1
        for i in range(self.n)[::-1]:
            self.counts[i] = self.counts[i*2] + self.counts[i*2 + 1]

    def query(self, left: int, right: int, threshold: int) -> int:
        left += self.n
        right += self.n + 1
        c = Counter()
        while left < right:
            if left % 2 == 1:
                c += self.counts[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                c += self.counts[right]
            right //= 2
            left //= 2
        topcount, topnum = max((ct, num) for num, ct in list(c.items()))
        return topnum if topcount >= threshold else -1
                
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)