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)