给定一个长度为 $n$ 的正整数数组，请您求出有多少个非空子数组满足：该非空子数组的正整数之和能被出现在该非空子数组中的最大数字。

$1\le n\le 10^5$。

标签：前缀和。

枚举数字 $d$ 从 $1$ 到 $9$（显然数字 $0$ 不可能成为最大数字）。将问题转化为计算满足正整数之和能被 $d$ 整除并且最大数字是 $d$ 的非空子数组的数量。

下面先考虑如何计算满足正整数之和能被 $d$ 整除的子数组数量。求出在模 $d$ 意义下的前缀和数组 $sum$，非空子数组 $[a_{l},\cdots,a_r]$ 能被 $d$ 整除的充要条件是 $sum_{l-1}=sum_{r}$。扫描整个数组并用一个计数数组即可计算数量。

下面考虑加上限制“最大数字是 $d$”。$i$ 从 $1$ 到 $n$ 扫描整个数组 $x_i$，并维护在模 $d$ 意义下的前缀和 $sum$、大小为 $d$ 的计数数组 $cnt$ 和用于暂时储存数值的容器 $vector$，最初把 $sum=0$ 存入 $vector$。

如果 $x_i$ 的最大数字小于 $d$，那么首先把 $cnt_{sum}$ 加入答案，然后把 $sum$ 存入 $vector$。

如果 $x_i$ 的最大数字等于 $d$，那么首先拿出 $vector$ 里的所有数值并把它们加入 $cnt$，然后把 $cnt_{sum}$ 加入答案，之后把 $sum$ 存入 $vector$。

如果 $x_i$ 的最大数字小于 $d$，那么首先清空 $cnt$ 和 $vector$，然后把 $sum$ 存入 $vector$。

时空复杂度：$O(n)$，含有常数 $9$。