Online Mode Frequency Query

Given an array of length \(n\) and \(m\) online queries, each query asks for the frequency of the mode (the most frequent element) in the specified subarray.

Note: You must answer the queries online.

More formally, you are given an array \(a[1 \dots n]\). For each query, given two integers \(l\) and \(r\) (1-indexed), output the maximum frequency among all elements in the subarray \(a[l \dots r]\). In case of ties (multiple elements having the same frequency), simply output the frequency.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the length of the array and the number of queries respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the array.

Each of the following \(m\) lines contains two integers \(l\) and \(r\) (1-indexed) denoting a query on the subarray \(a[l \dots r]\).

outputFormat

For each query, print a single integer in a new line, which is the frequency of the mode in the queried subarray.

sample

5 3
1 2 2 3 1
1 5
2 4
3 5

2
2
1