## Editorial for An Animal Contest 6 P3 - OAC

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: andrewtam, dxke02

Let's denote the array as and the length to be .

Observe that if the sum in the range is divisible by its length, then every element it contains must be equal to every other element.

With this in mind, we can solve this problem using the two-pointers technique.

Let's try to extend our observation from subtask 1. First note that if the sum of the subarray in the range is divisible by its length then we can write as for some .

Next, let's prove that always holds regardless of what subarray we choose. This is because we can use the fact that to prove that:

So:

With this in mind we can brute force all possible values of and for each of them check the number of subarrays whose sum can be written as .

For a given this is equivalent for finding the number of pairs such that:

Which can be rewritten as:

Where:

With this in mind, we can calculate the number of valid pairs for a given with a frequency table and a prefix sum array to quickly compute values of .

Time Complexity:

Consider using an array rather an unordered_map.