Problem 72: Highest Frequency Element in Subarray
Problem Statement: Given an array and q queries asking for the element with the highest frequency in a subarray, answer each query using Mo's algorithm.
Input
The first line contains integers n and q. The second line contains n integers. Then q lines follow, each with two integers l and r (1-indexed).
Output
For each query, print the element which occurs most frequently within the subarray. If multiple, print the smallest.
Examples
Input:
6 2
1 2 2 3 3 3
1 4
3 6
Output:
2
3
Solution Explanation
Using Mo's algorithm, maintain a frequency table and also track the candidate element for the mode. Update the candidate as the window moves. Resolve ties by taking the smallest element.
Solution in C++
[ a solution will be implemented when possible]