Problem Description

Given a string \( s \) of length \( n \), where \( s \) consists only of lowercase letters, find the number of non-empty substrings of \( s \) that are non-majority strings.

Definition: Non-empty Substring

Let \( s_i \) represent the \( i \)-th character of \( s \) (where \( 1 \leq i \leq n \)). For any two integers \( i \) and \( j \) (where \( 1 \leq i \leq j \leq n \)), the substring formed by \( s_i, s_{i+1}, \ldots, s_j \) in their original order is a non-empty substring of \( s \).
For example, when \( s = \texttt{abcde} \), substrings like \( \texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde} \) are non-empty substrings of \( s \), while \( \texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "} \) are not.

Definition: Non-Majority String

A string \( a \) is a non-majority string if the maximum occurrence of any character in \( a \) does not exceed \( \lfloor \frac{|a|}{2} \rfloor \). Here, \( \lfloor x \rfloor \) denotes the greatest integer less than or equal to \( x \), and \( |a| \) denotes the length of \( a \).

Input Format

A single line containing a string \( s \).

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

aabb

Sample Output #1

2

Sample Input #2

fqmdfnc

Sample Output #2

21

Notes

Sample 1 Explanation

Among the substrings, \( \texttt{ab} \) and \( \texttt{aabb} \) are non-majority non-empty substrings.

Data Range

For \( 100\% \) of the data, \( 1 \le n \le 500 \), and the string consists of lowercase letters.

见题面 Input 部分

见题面 Output 部分