Positive String

시간 제한2초메모리 제한1024 MB

요약

문자열 S의 연속 부분 문자열 중 뒤집은 문자열보다 사전순으로 큰 것의 개수를 센다.

문제

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$ .