题目描述

给定一个长度为 $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$ 的非空子串。

定义：非众数串

若字符串 $a$ 中出现次数最多的字符出现的次数不超过 $\lfloor |a|/2\rfloor$，则称字符串 $a$ 为一个非众数串。其中 $\lfloor x\rfloor$ 代表不超过 $x$ 的最大整数，$|a|$ 代表 $a$ 的长度。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

aabb

样例输出 #1

2

样例 #2

样例输入 #2

fqmdfnc

样例输出 #2

21

提示

样例 1 解释

子串 ab 和 aabb 是非众数串。

数据范围

对于 $100\%$ 的数据，$1\leq n\leq 500$，字符串由小写字母组成。