题目描述

给定一个由小写字母组成的字符串 $S$，求有多少个区间 $[l,r]$ 满足：

1. $S[l..r]$ 是回文串；
2. $S[l..r]$ 中每个字符的出现次数不超过 $2$。

输入格式

一行一个字符串 $S$（$|S|\le 5\times 10^4$）。

输出格式

一行一个整数，表示满足条件的区间数。

样例

ababa

8

提示

样例解释

对于 $S=$ ababa，满足条件的区间有 8 个。