Count Non-Majority Substrings

Given a string \(s\) of length \(n\) which contains only lowercase letters, count the number of its non-empty substrings that are non-majority substrings.

Definitions

Non-empty Substring
For \(s = s_1s_2\cdots s_n\), any string obtained by choosing two integers \(i, j\) with \(1 \le i \le j \le n\) and taking the contiguous segment \(s_i, s_{i+1}, \dots, s_j\) (in the same order) is called a non-empty substring. For example, if \(s = \texttt{abcde}\), then \(\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde}\) are non-empty substrings, while \(\texttt{acd}, \texttt{f}, \texttt{ngioasd}\) are not.

Non-Majority Substring
A substring \(a\) is called a non-majority substring if the number of occurrences of its most frequent character does not exceed \(\lfloor \frac{|a|}{2} \rfloor\). Here \(|a|\) is the length of \(a\) and \(\lfloor x \rfloor\) denotes the greatest integer less than or equal to \(x\).

inputFormat

The input consists of a single line containing the string \(s\), which is composed only of lowercase English letters.

outputFormat

Output a single integer representing the number of non-majority substrings of \(s\).

sample

a

0