Reverse Substring to Decrease Number

You are given a string s of length n consisting only of digit characters ('0' to '9'). You may consider this string as an n-digit decimal number, denoted as num (leading zeros are allowed).

You are allowed to select a contiguous substring of s and reverse it, at most once. Let the resulting number be denoted as \( num_{new} \). Your task is to count the number of different substring reversal operations (two operations are considered different if their positions in s differ) such that \( num_{new} < num \).

Note: Reversing a substring that is a palindrome will yield the same number and is not counted.

Explanation: Suppose you choose the substring s[l...r] (with \(0 \le l < r < n\)). After reversal, the new string becomes:

[ s_{new} = s[0\ldots l-1] + reverse(s[l\ldots r]) + s[r+1\ldots n-1]. ]

Since the prefix remains unchanged, the first position where the string may differ is at index l. Therefore, the condition \( num_{new} < num \) is equivalent to checking whether the digit s[r] (which moves to position l) is less than s[l], or, if they are equal, comparing subsequent corresponding digits until a difference is found. Formally, let \( t \) be the smallest integer (with \( 0 \le t \le r-l \)) for which \( s[l+t] \neq s[r-t] \). Then the operation is valid if and only if \( s[r-t] < s[l+t] \).

inputFormat

The input consists of a single line containing the string s which represents the number. The string is non-empty and consists only of digits (0-9).

outputFormat

Output a single integer representing the number of distinct substring reversal operations that yield a number strictly less than the original, i.e. satisfy \( num_{new} < num \).

sample

132

1