Count Groups

Twilio's IT team is trying to send two new USB Cables to all the Software Engineers. The problem is that there are a lot of USB standards and they are mostly not compatible with each other. For this reason, the team has labeled all the n cables with a numerical tag. They come in a list of tags like tags=[0,1,2,...] where the ith cable has the tags[i]. For example, if tags= [2,3,1,2], the cable number 2 would have the tag 3.

Now we want to group them in pairs taking into account that they must be of the same type. The restrictions for grouping are:

• Two cables can be formed together if they have the same tag.
• A group is always formed by 2 cables.
• One cable can only be in one 1 or 0 groups.

To do the most efficient distribution we want to create queries. A query has the form [left, right] and represents an interval in the list of cables. As a result of the query we want to retrieve the number of groups that can be formed. For example, if tags=[2,3,2,1] and the query=[1,3] we would take into consideration only the interval [2, 3, 2] and the number of groups would be 1 because we have two "2".

The queries come in a list of q queries like [[l1, r1], [l2, r2]...q times]. They are all independent of each other. The result must be in a list of groups formed for each query [r1,r2...q times].