[入门赛 #22] 非众数 Hard Version

题目背景

本题是「非众数」的 Hard Version,$1 \le n \le 10^5$,感谢 @[yummy](https://www.luogu.com.cn/user/101694) 的贡献。

题目描述

给定一个长度为 $n$ 的字符串 $s$,保证 $s$ 仅包含小写字母,求 $s$ 的**非空子串**中**非众数串**的个数。 > **定义:非空子串** > > 用 $s_i$ 表示 $s$ 中的第 $i$ 个字符($1 \leq i \leq n$)。任取两个整数 $i, j$($1 \leq i \leq j \leq n$),将 $s_i, s_{i + 1}, \cdots, s_{j}$ 截取出来按原序排列作为一个新的字符串,则这个字符串叫做 $s$ 的非空子串。 例如,当 $s = \texttt{abcde}$ 时,$\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde}$ 都是 $s$ 的非空子串,而 $\texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "}$ 都不是 $s$ 的非空子串。 > **定义:非众数串** > > 若字符串 $a$ 中出现次数最多的字符出现的次数不超过 $\lfloor \frac{|a|}{2} \rfloor$,则称字符串 $a$ 为一个**非众数**串。其中 $\lfloor x \rfloor$ 代表 $\leq x$ 的最大整数,$|a|$ 代表 $a$ 的长度。

输入输出格式

输入格式


一行一个字符串,表示 $s$。

输出格式


一行一个整数,表示答案。

输入输出样例

输入样例 #1

aabb

输出样例 #1

2

输入样例 #2

fqmdfnc

输出样例 #2

21

说明

### 样例 1 解释 其中 $\texttt{ab,aabb}$ 是**非众数**非空子串。 ### 数据范围 对于 $100\%$ 的数据,$1 \le n \le 10^5$,字符串由小写字母组成。