Redaksiya

Group 1: $n\le 200$

In this group, you can check all subsegments. Calculate the GCD and the arithmetic mean and check if they are equal.

Solution complexity: $O(n^3)$

Group 2: $n\le 2000$

In this group, you can iterate through all subsegments, but do it a bit smarter.

for (int l = 0 ; l < n ; l++)
    for (int r = l ; r < n ; r++)

By iterating through the segments in this way, we can maintain the GCD and the sum.

Solution complexity: $O(n^2\ast log(C)$ where $C$ is the maximal possible element from the array $a$.

Group 3: $n\le 100000$ (no restrictions)

You can notice the following fact: if a subarray is good, then all numbers in it are equal.

Proof: Let's take the minimum element, denote it as m, its GCD as g, and the arithmetic mean as s. Since m is divisible by g, then $m\ge g$, and at the same time $s\ge m$, then $s\ge m\ge g$, and at the same time $s=g$, then $s=m=g$, which means that all numbers are equal.

If we use this fact, then we need to find the maximum length subsegment of equal numbers and the number of such subsegments.

This problem can be solved as follows: divide the array into blocks of equal numbers, the maximum subsegment will be the maximum length of a block, and the count can be calculated for each block separately using the formula $k\ast (k+1)/2$, where k is the size of the block.

Solution complexity: $O(n)$