Problem Description

Xiao Lan has a string of length $n$ consisting only of digit characters $0 \sim 9$, with indices from $0$ to $n - 1$. You can treat it as an $n$-digit decimal number $num$. Xiao Lan can choose a continuous substring of $num$ and reverse that substring, at most once. Xiao Lan wants the new number $num_{new}$ obtained by reversing the chosen substring and putting it back into its original position to satisfy $num_{new} < num$. Please help him compute how many different substring choices there are in total. As long as the positions of the two substrings in $num$ are not exactly the same, we consider them different choices.

Note that leading zeros are allowed, i.e., the most significant digit of the number may be $0$, and this is valid.

Input Format

Input one line containing a string of length $n$ representing $num$ (containing only digit characters $0 \sim 9$). From left to right, the indices are $0 \sim n - 1$.

Output Format

Output one line containing an integer representing the answer.

210102

8

Hint

Sample Explanation.

There are $8$ different choices in total:

1. The chosen substring indices are $0 \sim 1$, after reversing $num_{new} = 120102 < 210102$.
2. The chosen substring indices are $0 \sim 2$, after reversing $num_{new} = 012102 < 210102$.
3. The chosen substring indices are $0 \sim 3$, after reversing $num_{new} = 101202 < 210102$.
4. The chosen substring indices are $0 \sim 4$, after reversing $num_{new} = 010122 < 210102$.
5. The chosen substring indices are $0 \sim 5$, after reversing $num_{new} = 201012 < 210102$.
6. The chosen substring indices are $1 \sim 2$, after reversing $num_{new} = 201102 < 210102$.
7. The chosen substring indices are $1 \sim 4$, after reversing $num_{new} = 201012 < 210102$.
8. The chosen substring indices are $3 \sim 4$, after reversing $num_{new} = 210012 < 210102$.

Constraints.

For $20\%$ of the testdata, $1 \le n \le 100$.

For $40\%$ of the testdata, $1 \le n \le 1000$.

For all testdata, $1 \le n \le 5000$.

Translated by ChatGPT 5