import sys
input = sys.stdin.read
from collections import defaultdict
from math import sqrt
# Function to preprocess data for faster queries
def preprocess_array(A, N):
# Stores occurrences of each element at each index
positions = defaultdict(list)
for i in range(N):
positions[A[i]].append(i)
return positions
# Binary search to count occurrences in a range [l, r]
def count_in_range(positions, x, l, r):
from bisect import bisect_left, bisect_right
pos_list = positions[x]
return bisect_right(pos_list, r) - bisect_left(pos_list, l)
def process_queries(N, Q, A, queries):
# Step 1: Preprocess the positions of each element in the array
positions = preprocess_array(A, N)
results = []
# Step 2: Process each query
for l, r in queries:
l -= 1 # convert to 0-based index
r -= 1
threshold = (r - l + 1) // 3
found = -1
# Collect potential candidates (at most 2 elements)
candidates = set(A[l:r+1][:2]) # take first two elements in range as starting candidates
for candidate in candidates:
# Count occurrences of candidate in range [l, r]
count = count_in_range(positions, candidate, l, r)
if count > threshold:
if found == -1 or candidate < found:
found = candidate
# Append the result for this query
results.append(str(found))
return "\n".join(results)
# Main function to handle input and output
def main():
data = input().split()
idx = 0
N = int(data[idx])
Q = int(data[idx + 1])
idx += 2
A = list(map(int, data[idx:idx + N]))
idx += N
queries = []
for _ in range(Q):
l = int(data[idx])
r = int(data[idx + 1])
queries.append((l, r))
idx += 2
results = process_queries(N, Q, A, queries)
print(results)