Time Limit: 2.5 s

Memory Limit: 256.0 MB

Description

In a serene kingdom hidden among lush hills, there lies a secret garden filled with extraordinary plants, each represented by an integer in an enchanted array A of size N. This garden is watched over by a wise old gardener who has devised a series of mystical quests for curious adventurers eager to unlock its secrets.

Each adventurer must navigate through the garden by answering Q queries, each defined by a pair of integers l and r that indicate a specific range of plants to investigate. Their task is to find the minimum integer X within the specified range [l, r] that appears with a frequency greater than (r - l + 1) / 3. This means X should not only be a contender but must also flourish more abundantly than one-third of the total plants in that range, ensuring it is the minimal integer meeting the condition.

However, if the adventurers search thoroughly and find no integer that meets this requirement, they must humbly report their failure with a declaration of -1, indicating that the sought-after plant remains elusive.

Input

The first line contains two integers: N(size of the array) and Q(number of query) (1 <= N , Q <= \(2 * 10^5\)).
The second line contains N integers \(A_1\) , \(A_2\) ,,, \(A_N\) (1 ≤ \(A_i\) ≤ N), where \(A_i\) represents the various plants in the garden.
The next Q lines each contain two integers l and r (1 <= l <= r <= N), defining the range for each query.

Output

For each query, provide the minimum integer X that appears with a frequency greater than (r - l + 1) / 3, or -1 if no such integer exists.

Sample

7 3
2 3 4 2 1 1 1
1 4
1 6
1 7

2
-1
1