P9232 [Lanqiao Cup 2023 NOI Qualifier A] Smaller Number

 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 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 one line containing an integer representing the answer.

#### 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