Recently I tried to solve Loj-1339 and found some ideas.

The main problem is :

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.

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).

It can be done with Mo' algorithm. If I was told to find number of distinct integers from i to j then I can easily find the answer using Mo. but problems occur when max-min is wanted. I'm not able to keep track of the maximum community. When I add values, I can do this, but while removing,I can't find out a way to track the maximum. One of my friends told me to make a sqrt decomposition for the array. After adding/removing, somehow we have to maintain the aux[] array, and for queries, suppose we have sqrt(n) blocks, then from i to j, if any block is fully inside i and j then we just take the max from the block Id and if it doesn't , we just loop through the array. But I am not sure about this idea, also I can't implement it properly, can you please help me about this problem ? Thanks in advance.