T581164 「2025 扬大ACM选拔赛」H - Sweet interval

MilkDragon has recently collected $n$ jars of candy in a row. The number of candies in each jar forms an array $a$, where $a_i$ represents the number of candies in the $i$-th jar. MilkDragon wants to play a ‘sweet interval’ game with his best friends. For any two positions $1 \le l \le r \le n$, define a magic function: $$ f(l,r)=\left\lfloor \frac{ \sum_{i=l}^r a_i }{r-l+1} \right\rfloor $$ This represents the **floor value** of the number of candies each person would get if the candies from the $l$-th jar to the $r$-th jar were **evenly divided** among the $(r-l+1)$ peeps (by chopping off the fractional part directly)! Let $v= \max_{1\le l \le r \le n}f(l,r)$, and now MilkDragon wants to know： Among all possible intervals $(i, j)$ with $1\leq i\leq j\leq n$, **how many intervals can achieve the maximum value $v$** ?

The first line contains an integer $n~$ ($1 \le n \le 2 \cdot 10^5$) — the length of $a$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n~$ ($-10^9 \le a_i \le 10^9$) — the elements of $a$.

output the number of pairs of integers satisfying the conditions.