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

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Range queries

Segment trees revisited

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:
		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


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


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


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


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)

	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


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


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


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


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


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


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


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


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):
			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


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


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


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]
		elif lf > rf:
			return [lv, lf - rf]
		else:
			return [rv, rf - lf]


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


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


from collections import defaultdict
import bisect

class MajorityChecker:

	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


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 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
				elif 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)
			elif 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


from collections import defaultdict
import bisect

class MajorityChecker:

	def __init__(self, arr: List[int]):
		self.d = defaultdict(list)
		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:
		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


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


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


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


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)
		if candidate.val == 0:
			return -1
		s = self.lower_bound(self.freq[candidate.val], left)
		e = self.upper_bound(self.freq[candidate.val], right)
		if e - s >= threshold:
			return candidate.val
		else:
			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
		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


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


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
			if right_i - left_i + 1 >= threshold:
				return self.arr[x]
			length = length - (right_i - left_i + 1)
			if threshold > length:
				return -1
			visited.add(self.arr[x])
		return -1


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)
			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


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)


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


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 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)


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
		while r > l:
			m = (r + l) // 2
			if self.numDict[num][m] < left:
				l = m + 1
			else:
				r = m
		return right - l + 1


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):
			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
			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
			if end - start + 1 >= threshold:
				return True
			else:
				return False
		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


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)


from collections import Counter

class Node(object):

	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):
		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):
		res = self.root.count.copy()
		sentinel = False

		def helper(node):
			nonlocal res, l, r, sentinel, threshold
			if sentinel:
				return None
			if not res or max(res.values()) < threshold:
				sentinel = True
				res = {}
				return None
			(i, j) = node.val
			if j < l or i > r:
				res -= node.count
				return None
			if l <= i and j <= r:
				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:
		(val, freq) = self.tree.find_most_common(left, right, threshold)
		return val if freq >= threshold else -1


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


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


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


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
				elif 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
			elif 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 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:
		for num in self.nums:
			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


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


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