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.