Contiguous Subarray Maximum Frequency Query

Given an array of n integers and q queries, each query specified with two indices l and r (1-indexed), your task is to find the maximum frequency among the integers in the contiguous subarray defined from index l to r. In other words, for each query, calculate the frequency of each distinct number in the segment arr[l-1] ... arr[r-1] and output the maximum count. This problem often appears as a subtask in competitions where subarray statistics are required.

Formal Description:

Given an array \(A = [a_1, a_2, \dots, a_n]\) and a query \((l, r)\), let \(f(x)\) be the frequency of number \(x\) in the subarray \(A[l, r]\). The answer for the query is \(\max_{x \in A[l, r]} f(x)\).

Examples:

• For A = [1, 2, 2, 3, 3, 3] and query \((1, 3)\), the subarray is \([1, 2, 2]\) and the maximum frequency is 2.
• For the same array and query \((2, 6)\), the subarray is \([2, 2, 3, 3, 3]\) and the maximum frequency is 3.

inputFormat

The first line contains three space-separated integers: n (size of the array), m (maximum possible value in the array), and q (number of queries).

The second line contains n space-separated integers, representing the array elements.

Each of the next q lines contains two space-separated integers l and r, representing a query on the subarray from index l to r (1-indexed).

outputFormat

For each query, output a single integer on a new line: the maximum frequency among numbers in the subarray defined by the query.

## sample

6 5 1
1 2 2 3 3 3
1 3

2

</p>