25701번 - Positive String 다국어

문제

Grammy had a unique insight about strings. She thinks that a string is positive if and only if it is lexicographically larger than its reversal.

Now you are given a string, please find out how many contiguous substrings of it are positive according to Grammy's insight.

입력

The single line contains a string $S$ (1ドル \leq |S| \leq 200,000円$), consisting of lowercase English letters only.

출력

Output a single integer denoting the number of positive substrings of $S$.

제한

힌트