Counting Novel Dance Subarrays

Yazid has a sequence (A) of length (n) with indices from (1) to (n). There are (\frac{n(n+1)}{2}) possible subarrays. For any subarray ([l,r]), if the mode in the subarray appears strictly more than (\frac{r-l+1}{2}) times, then the subarray is considered to be a novel dance subarray.

The mode is defined as the number that occurs most frequently in the subarray. In the event of a tie (i.e. more than one number attaining the maximum frequency), the smallest number is chosen as the mode.

Your task is to count how many subarrays of (A) are novel dance subarrays.

Note on Formulae: All formulas are presented in (\LaTeX) format. For instance, the total number of subarrays is given by (\frac{n(n+1)}{2}) and the condition for a subarray ([l,r]) to be novel is that if (f) is the frequency of its mode, then [ f > \frac{r-l+1}{2}. ]

inputFormat

The first line contains an integer (n), the length of the sequence. The second line contains (n) space-separated integers, representing the sequence (A).

outputFormat

Output a single integer: the number of novel dance subarrays.

sample

3
1 1 2

5