Server Time: Sun Oct 25, 2020 4:52 pm
 Welcome ( logout )
1339 - Strongest Community
 PDF (English) Statistics Forum
 Time Limit: 3 second(s) Memory Limit: 64 MB

In a strange city, houses are built in a straight line one after another. There are several communities in the city. Each community consists of some consecutive houses such that every house belongs to exactly one community. The houses are numbered from 1 to n, and the communities are numbered from 1 to c.

Now some inspectors want to find the strongest community considering all houses from i to j. A community is strongest if maximum houses in the range belong to this community. So, there can be more than one strongest community in the range. So, they want to know the number of houses that belong to the strongest community. That's why they are seeking your help.

# Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing three integers n (1 ≤ n ≤ 105), c (1 ≤ c ≤ n) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers (each between 1 and c) denoting the communities the houses belong to. You can assume that the input follows the restrictions given above, and there are exactly c communities.

Each of the next q lines contains two integers i and j (1 ≤ i ≤ j ≤ n) denoting that the inspectors are asking for the result considering houses from i to j (inclusive).

# Output

For each case, print the case number in a single line. Each of the next q lines should contain the number of houses that belong to the strongest community considering houses from i to j. The result should be listed in the same order as they are given in input.

# Output for Sample Input

2

10 3 4

1 1 1 3 3 3 3 2 2 2

1 5

1 6

1 7

7 9

3 3 1

3 2 1

1 1

Case 1:

3

3

4

2

Case 2:

1

# Note

Dataset is huge, use faster I/O methods.

Problem Setter: Jane Alam Jan
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan