UAIC Competitive Programming

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]